An optimal algorithm for the boundary of a cell in a union of rays. (English) Zbl 0697.68030

Summary: We study a cell of the subdivision induced by a union of n half-lines (or rays) in the plane. We present two results. The first one is a novel proof of the O(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal \(\Theta\) (n log n) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.


68Q25 Analysis of algorithms and problem complexity
68U99 Computing methodologies and applications
68R99 Discrete mathematics in relation to computer science
Full Text: DOI


[1] P. Alevizos, J. D. Boissonnat, and M. Yvinec: An OptimalO(n logn) Algorithm for Contour Reconstruction from Rays,Proc. 3rd ACM Symposium on Computational Geometry, Waterloo, pp. 162-170, June 1987.
[2] M. Atallah: Dynamic Computational Geometry,Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 92-99, Oct. 1983.
[3] B. Chazelle and L. Guibas: Visibility and Intersection Problems in Plane Geometry,Proc. 1st ACM Symposium on Computational Geometry, Baltimore, pp. 135-147, June 1985. · Zbl 0695.68033
[4] Chazelle, B.; Guibas, L.; Lee, D. T., The Power of Geometric Duality, BIT, 25, 76-90 (1985) · Zbl 0603.68072
[5] H. Edelsbrunner, L. J. Guibas, and M. Sharir: The Complexity of Many Faces in Arrangements of Lines and Segments,Proc. 4th ACM Symposium on Computational Geometry, Urbana, pp. 44-56, June 1988. · Zbl 0691.68035
[6] Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing Arrangements of Lines and Hyper-planes with Applications, SIAM J. Comput., 15, 341-363 (1986) · Zbl 0603.68104
[7] L. J. Guibas, M. Sharir, and S. Sifrony: On the General Motion Planning Problem with Two Degrees of Freedom,Proc. 4th ACM Symposium on Computational Geometry, Urbana, pp. 319-329, June 1988. · Zbl 0685.68049
[8] Hart, S.; Sharir, M., Non-Linearity of Davenport-Schinzel Sequences and of Generalized Path Compression Schemes, Combinatorica, 6, 2, 151-177 (1986) · Zbl 0636.05003
[9] Pollack, R.; Sharir, M.; Sifrony, S., Separating Two Simple Polygons by a Sequence of Translations, Discrete Comput. Geom., 3, 123-136 (1988) · Zbl 0646.68052
[10] Wiernik, A.; Sharir, M., Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments, Discrete Comput. Geom., 3, 15-47 (1988) · Zbl 0636.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.