Position-independent street searching
| dc.contributor.author | Hipke, Christoph, A. | |
| dc.contributor.author | Lopez-Ortizt, Alejandro | |
| dc.date.accessioned | 2023-03-01T18:27:42Z | |
| dc.date.available | 2023-03-01T18:27:42Z | |
| dc.date.issued | 1999 | |
| dc.description.abstract | A polygon P is a street if there exist points (u, v) on the boundary such that P is weakly visible from any path from u to v. Optimal strategies have been found for on-line searching of streets provided that the starting position of the robot is s = u and the target is located at t = v. Thus a hiding target could foil the strategy of the robot by choosing its position tin such a manner as not to realize a street. In this paper we introduce a strategy with a constant competitive ratio to search a street polygon for a target located at an arbitrary point ton the boundary, starting for any other arbitrary point s on the boundary. We also provide lower bounds for this problem. This makes streets only the second non-trivial class of polygons (after stars) known to admit a constant-competitive-ratio strategy in the general case. | |
| dc.description.copyright | Copyright @ Christoph A. Hipke and Alejandro Lopez-Ortizt, 1999. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14772 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | Position-independent street searching | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1