Abstract
\(\beta \)-skeletons are well-known neighborhood graphs for a set of points. We extend this notion to sets of line segments in the Euclidean plane and present algorithms computing such skeletons for the entire range of \(\beta \) values. The main reason of such extension is the possibility to study \(\beta \)-skeletons for points moving along given line segments. We show that relations between \(\beta \)-skeletons for \(\beta > 1\), 1-skeleton (Gabriel Graph), and the Delaunay triangulation for sets of points hold also for sets of segments. We present algorithms for computing circle-based and lune-based \(\beta \)-skeletons. We describe an algorithm that for \(\beta \ge 1\) computes the \(\beta \)-skeleton for a set S of n segments in the Euclidean plane in \(O(n^2 \alpha (n) \log n)\) time in the circle-based case and in \(O(n^2 \lambda _4(n))\) in the lune-based one, where the construction relies on the Delaunay triangulation for S, \(\alpha \) is a functional inverse of Ackermann function and \(\lambda _4(n)\) denotes the maximum possible length of a (n, 4) Davenport-Schinzel sequence. When \(0 < \beta < 1\), the \(\beta \)-skeleton can be constructed in a \(O(n^3 \lambda _4(n))\) time. In the special case of \(\beta = 1\), which is a generalization of Gabriel Graph, the construction can be carried out in a \(O(n \log n)\) time.
This research is supported by the ESF EUROCORES program EUROGIGA, CRP VORONOI.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aichholzer, O., Aurenhammer, F.: Straight skeletons for general polygonal figures in the plane. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol. 1090, pp. 117–126. Springer, Heidelberg (1996)
Brévilliers, M., Chevallier, N., Schmitt, D.: Triangulations of line segment sets in the plane. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 388–399. Springer, Heidelberg (2007)
Burnikel, C., Mehlhorn, K., Schirra, S.: How to compute the voronoi diagram of line segments: theoretical and experimental results. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 227–239. Springer, Heidelberg (1994)
Chew, L.P., Kedem, K.: Placing the largest similar copy of a convex polygon among polygonal obstacles. In: Proceedings of the 5th Annual ACM Symposium on Computational Geometry, pp. 167–174 (1989)
Eppstein, D.: \(\beta \)-skeletons have unbounded dilation. Comput. Geom. 23, 43–52 (2002)
Goodman, J.E., O’Rourke, J.: Handbook of Discrete and Computational Geometry. Chapman & Hall/CRC, New York (2004)
Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Zool. 18, 259–278 (1969)
Hershberger, J.: Finding the upper envelope of n line segments in O(n log n) time. Inf. Process. Lett. 33(4), 169–174 (1989)
Hurtado, F., Liotta, G., Meijer, H.: Optimal and suboptimal robust algorithms for proximity graphs. Comput. Geom. Theory Appl. 25(1–2), 35–49 (2003)
Jaromczyk, J.W., Kowaluk, M.: A note on relative neighborhood graphs. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, Canada, Waterloo, pp. 233–241. ACM Press (1987)
Kirkpatrick, D.G., Radke, J.D.: A framework for computational morphology. In: Computational Geometry, pp. 217–248. North Holland, Amsterdam (1985)
Kowaluk, M.: Planar \(\beta \)-skeleton via point location in monotone subdivision of subset of lunes. In: EuroCG, Italy. Assisi 2012, pp. 225–227 (2012)
Lingas, A.: A linear-time construction of the relative neighborhood graph from the Delaunay triangulation. Comput. Geom. 4, 199–208 (1994)
Matula, D.W., Sokal, R.R.: Properties of Gabriel graphs relevant to geographical variation research and the clustering of points in plane. Geog. Anal. 12, 205–222 (1984)
Papadopoulou, E., Zavershynskyi, M.: A Sweepline Algorithm for Higher Order Voronoi Diagrams, In: Proceedings of 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), pp. 16–22 (2013)
Supowit, K.J.: The relative neighborhood graph, with an application to minimum spanning trees. J. ACM 30(3), 428–448 (1983)
Toussaint, G.T.: The relative neighborhood graph of a finite planar set. Pattern Recognit. 12, 261–268 (1980)
Acknowledgments
The authors would like to thank Jerzy W. Jaromczyk for important comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kowaluk, M., Majewska, G. (2015). \(\beta \)-skeletons for a Set of Line Segments in \(R^2 \) . In: Kosowski, A., Walukiewicz, I. (eds) Fundamentals of Computation Theory. FCT 2015. Lecture Notes in Computer Science(), vol 9210. Springer, Cham. https://doi.org/10.1007/978-3-319-22177-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-22177-9_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22176-2
Online ISBN: 978-3-319-22177-9
eBook Packages: Computer ScienceComputer Science (R0)