Computing External-Farthest Neighbors for a Simple Polygon (Classic Reprint) - Tapa blanda

Reseña del editor

Excerpt from Computing External-Farthest Neighbors for a Simple Polygon

Shortest path planning in an Obstacle-cluttered environment is a classical problem in computational geometry. In two dimensions, it is common to model the Obstacles by closed simple polygons PI Pm whose interiors represent forbidden regions, and to model a robot by a point. A feasible path Of the robot in such an environment is a path that does not meet the interior Of the Obstacles. Given two points in the plane, the distance between them is the length Of the shortest feasible path connecting them; if either Of the points lies inside an Obstacle, this distance is assumed to be infinite.

The set u,p; is called the obstacle space. A useful measure of the Obstacle space is the maximum distance between any two points lying on its boundary. This maximum distance is called the diameter Of the Obstacle space. In this paper, we are concerned with the case Of a single Obstacle.

Given a simple n-gon P and two points p and g on its boundary, we define the external distance between p and q to be the length Of a shortest path that joins p and q without intersecting the interior Of P. For a vertex p Of P, let d(p) be the set Of points on (the boundary Of) P that are farthest from p with respect to the external distance, and let the external diameter Of P be the maximum external distance between any two points Of P. The problem of computing the external diameter was first considered by Samuel and Toussaint [sts7]. They presented an 0(uz) time algorithm to solve the problem, where n denotes the number Of vertices Of P.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.