Title :
On some link distance problems in a simple polygon
Author_Institution :
Johns Hopkins Univ., Baltimore, MD, USA
fDate :
2/1/1990 12:00:00 AM
Abstract :
A technique is presented for preprocessing a simple polygon to answer link distance queries. The preprocessing requires linear time and the time to triangulate the polygon, and it uses linear storage. As an application of the technique, optimal algorithms for several fundamental link distance problems are derived
Keywords :
computational complexity; computational geometry; computational complexity; computational geometry; link distance problems; polygon; triangulation; Microwave communication; Motion planning; Navigation; Path planning; Repeaters; Robots; Shortest path problem; Transmitters; Tree graphs; Turning;
Journal_Title :
Robotics and Automation, IEEE Transactions on
