Abstract
The concept of convex polygon-offset distance function was introduced in 2001 by Barequet, Dickerson, and Goodrich. Using this notion of point-to-point distance, they showed how to compute the corresponding nearest- and farthest-site Voronoi diagram for a set of points. In this paper we generalize the polygon-offset distance function to be from a point to any convex object with respect to an m-sided convex polygon, and study the nearest- and farthest-site Voronoi diagrams for sets of line segments and convex polygons. We show that the combinatorial complexity of the nearest-site Voronoi diagram of n disjoint line segments is O(nm), which is asymptotically equal to that of the Voronoi diagram of n point sites with respect to the same distance function. In addition, we generalize this result to the Voronoi diagram of disjoint convex polygonal sites. We show that the combinatorial complexity of the nearest-site Voronoi diagram of n convex polygonal sites, each having at most k sides, is \(O(n(m+k))\). Finally, we show that the corresponding farthest-site Voronoi diagram is a tree-like structure with the same combinatorial complexity.
M. De—Supported by DST-INSPIRE Faculty Grant (DST-IFA14-ENG-75).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A disadvantage of this approach is that relabeling of the input sites will change the diagram. One can adopt the rule of Klein and Wood [12], who break ties by the lexicographic order of the input points, but with such a solution, the Voronoi diagram will not be invariant under rotation of the plane.
References
Aurenhammer, F., Drysdale, R.L.S., Krasser, H.: Farthest line segment Voronoi diagrams. Inf. Process. Lett. 100(6), 220–225 (2006)
Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)
Barequet, G., Dickerson, M.T., Goodrich, M.T.: Voronoi diagrams for convex polygon-offset distance functions. Discret. Comput. Geom. 25(2), 271–291 (2001)
Bohler, C., Cheilaris, P., Klein, R., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. Comput. Geom. Theory Appl. 48(8), 539–551 (2015)
Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., Na, H.-S.: Farthest-polygon Voronoi diagrams. Comput. Geom. Theory Appl. 44(4), 234–247 (2011)
Chew, L.P., Drysdale III, R.L.S.: Voronoi diagrams based on convex distance functions. In: O’Rourke, J. (ed.) Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, 5–7 June 1985, pp. 235–244. ACM (1985)
Descartes, R.: Principia Philosophiae. Ludovicus Elzevirius, Amsterdam (1644)
Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153–174 (1987)
Kelley, J.L., Namioka, I.: Linear Topological Spaces. Springer, Heidelberg (1976)
Kirkpatrick, D.G.: Efficient computation of continuous skeletons. In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29–31 October 1979, pp. 18–27. IEEE Computer Society (1979)
Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400. Springer, Heidelberg (1989)
Klein, R., Wood, D.: Voronoi diagrams based on general metrics in the plane. In: Cori, R., Wirsing, M. (eds.) STACS 1988. LNCS, vol. 294, pp. 281–291. Springer, Heidelberg (1988). doi:10.1007/BFb0035852
Leven, D., Sharir, M.: Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams. Discret. Comput. Geom. 2, 9–31 (1987)
McAllister, M., Kirkpatrick, D.G., Snoeyink, J.: A compact piecewise-linear Voronoi diagram for convex sites in the plane. Discret. Comput. Geom. 15(1), 73–105 (1996)
Mehlhorn, K., Meiser, S., Rasch, R.: Furthest site abstract Voronoi diagrams. Int. J. Comput. Geom. Appl. 11(6), 583–616 (2001)
Papadopoulou, E., Dey, S.K.: On the farthest line-segment Voronoi diagram. Int. J. Comput. Geometry Appl. 23(6), 443–460 (2013)
Yap, C.-K.: An O\((n \log n)\) algorithm for the Voronoi diagram of a set of simple curve segments. Discret. Comput. Geom. 2, 365–393 (1987)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Barequet, G., De, M. (2017). Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function. In: Gaur, D., Narayanaswamy, N. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2017. Lecture Notes in Computer Science(), vol 10156. Springer, Cham. https://doi.org/10.1007/978-3-319-53007-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-53007-9_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53006-2
Online ISBN: 978-3-319-53007-9
eBook Packages: Computer ScienceComputer Science (R0)