the all-geodesic furthest neighbor problem for simple polygons
We present an &Ogr; ( n log n ) time and &Ogr; ( n ) space algorithm for the following problem in a simple polygon P with n vertices: For each vertex u of P , find another vertex &pgr;( u ) that is furthest from u , where the distance between two points is measured by the length of the shortest internal path connecting them in P . As a corollary, the longest internal path in P , called the geodesic diameter, also can be found within the same time and space bound. All the previously known algorithms for computing the geodesic diameter have required &OHgr;( n 2 ) time in the worst case, e.g. see Chazelle [5], Reif and Storer [16] and Toussaint [19].
polygon timing space algorithm distance point intern computation case