The geodesic farthest-site Voronoi diagram in a polygonal domain with holes

ABSTRACT

We investigate the farthest-site Voronoi diagram of k point sites with respect to the geodesic distance in a polygonal domain of n corners and h (≥ 0) holes. In the case of h=0, Aronov et al. [2] in 1993 proved that there are at most O(k) faces in the diagram and the complexity of the diagram is at most O(n+k). However, any nontrivial upper bound on the geodesic farthest-site Voronoi diagram in a polygonal domain when h > 0 remains unknown afterwards. In this paper, we show that the diagram in a polygonal domain consists of Θ(hk) faces and its total combinatorial complexity is Θ(nk) in the worst case for any h ≥ 1. Interestingly, the worst-case complexity of the diagram is independent from the number h of holes if h ≥ 1 while the maximum possible number of faces is dependent on h rather than on the complexity n of the polygonal domain. Also, we present an O(nk log²(n+k) log k)-time algorithm that constructs the diagram explicitly.

REFERENCES

• 1: B. Aronov. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica, 4(1-4):109--140, 1989.
• 2: B. Aronov, S. Fortune, and G. Wilfong. The furthest-site geodesic Voronoi diagram. Discrete Comput. Geom., 9:217--255, 1993.
• 3: O. Cheong, H. Everett, M. Glisse, J. Gudmundsson, S. Hornus, S. Lazard, M. Lee, and H.-S. Na. Farthest-polygon Voronoi diagrams. In Proc. 15th Annu. Euro. Sympos. Algo., volume 4698 of LNCS, pages 407--418, 2007.
• 4: L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, v.39 n.2, p.126-152, Oct. 1989 [doi>10.1016/0022-0000(89)90041-X]
• 5: John Hershberger , Subhash Suri, Matrix searching with the shortest path metric, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.485-494, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167220]
• 6: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 7: K. Mehlhorn, S. Meiser, and R. Rasch. Furthest site abstract Voronoi diagrams. Internat. J. Comput. Geom. Appl., 11(6):583--616, 2001.
• 8: J. S. B. Mitchell. Shortest paths among obstacles in the plane. Internat. J. Comput. Geom. Appl., 6(3):309--331, 1996.
• 9: Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 10: J. R. Munkres. Topology. Prentice Hall, Inc., second edition, 2000.
• 11: J. O'Rourke and S. Suri. Polygons. In Handbook of discrete and computational geometry, chapter 26, pages 583--606. CRC Press, Inc., Boca Raton, FL, USA, 2nd edition, 2004.
• 12: E. Papadopoulou and D. T. Lee. A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica, 20(4):319--352, 1998.
• 13: R. Pollack , M. Sharir , G. Rote, Computing the geodesic center of a simple polygon, Discrete & Computational Geometry, v.4 n.6, p.611-626, Sep. 1989 [doi>10.1007/BF02187751]
• 14: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 15: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 16: S. Suri, Computing geodesic furthest neighbors in simple polygons, Journal of Computer and System Sciences, v.39 n.2, p.220-235, Oct. 1989 [doi>10.1016/0022-0000(89)90045-7]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
farthest-site voronoi diagram, geodesic, polygonal domain, shortest obstacle-free path, tight upper bound