Name
Abstract | ||
|---|---|---|
Exploring a polygon is the problem of a robot that does not have a map of its surroundings to see the complete polygon. In other words, for the robot to construct a map of the polygon. Exploration can be viewed as an online problem. Typical for online problems is that the solution method must make decisions based on past events but without knowledge about the future. In our case the robot does not have complete information about the environment. Competitive analysis can be used to measure the performance of methods solving online problems. The competitive factor of such a method is the ratio between the method's performance and the performance of the best method having full knowledge about the future. We prove a 5/3-competitive strategy for exploring a simple rectilinear polygon in the L1 metric. This improves the previous factor two bound of Deng, Kameda and Papadimitriou. |
Year | Venue | Keywords |
|---|---|---|
2002 | Nord. J. Comput. | improved exploration,previous factor,complete information,competitive factor,solution method,complete polygon,competitive analysis,simple rectilinear polygon,online problem,full knowledge,best method,online algorithms,computational geometry |
Field | DocType | Volume |
Online algorithm,Rectilinear polygon,Polygon,Computer science,Computational geometry,Theoretical computer science,Point in polygon,Robot,Complete information,Competitive analysis | Journal | 9 |
Issue | Citations | PageRank |
1 | 3 | 0.40 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikael Hammar | 1 | 163 | 16.22 |
| Bengt J. Nilsson | 2 | 210 | 24.43 |
| Sven Schuierer | 3 | 308 | 29.35 |