dc.creator | Fleischer, Rudolf | es |
dc.creator | Kamphans, Tom | es |
dc.creator | Klein, Rolf | es |
dc.creator | Langetepe, Elmar | es |
dc.creator | Trippen, Gerhard | es |
dc.date.accessioned | 2017-03-02T11:30:06Z | |
dc.date.available | 2017-03-02T11:30:06Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | Fleischer, R., Kamphans, T., Klein, R., Langetepe, E. y Trippen, G. (2004). Competitive search ratio of graphs and polygons. En 20th European Workshop on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/55109 | |
dc.description.abstract | We consider the problem of searching for a goal in an unknown environment, which may be a graph or a polygonal environment. The search ratio is the worst-case ratio before the goal is found while moving along some search path, over the shortest path from the start point to the goal, minimized over all search paths. We investigate the problem of finding good approximations to the optimal search path, with or without a priori knowledge of the environment. In the latter case, we are dealing with an online problem. We must compute a good search path while exploring the unknown environment. We present a unified framework that allows us to derive competitive search path algorithms from existing competitive exploration algorithms, if it is possible to modify them in a certain natural way. Our transformation increases the competitive ratio at most by a factor of eight. This expresses the relationship between competitive online exploration and online searching more precisely than before. We apply our framework to searching in trees, (planar) graphs, and in (rectilinear) polygonal environments with or without holes. | es |
dc.description.sponsorship | Research Grants Council of the Hong Kong Special Administrative Region, China | es |
dc.description.sponsorship | Germany/Hong Kong Joint Research Scheme | es |
dc.description.sponsorship | Research Grants Council of Hong Kong | es |
dc.description.sponsorship | German Academic Exchange Service | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | 20th European Workshop on Computational Geometry (2004). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Online motion planning | es |
dc.subject | Competitive ratio | es |
dc.subject | Searching | es |
dc.subject | Exploration | es |
dc.subject | Search ratio | es |
dc.title | Competitive search ratio of graphs and polygons | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.relation.projectID | HKUST6010/01E | es |
dc.relation.projectID | G-HK024/02 | es |
dc.relation.projectID | DAAD/RGC 2003/2004 | es |
idus.format.extent | 4 p. | es |
dc.eventtitle | 20th European Workshop on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |