Arrangements of curves in the plane - topology, combinatorics, and algorithms

H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, in:, Springer, 1988, pp. 214–229.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ; ; ;
Series Title
LNCS
Abstract
Arrangements of curves in the plane are of fundamental significance in many problems of computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves), and an application of (some weaker variant of) that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.
Publishing Year
Date Published
1988-01-01
Acknowledgement
Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under grant CCR-8714566.
Volume
317
Page
214 - 229
Conference
ICALP: Automata, Languages and Programming
IST-REx-ID

Cite this

Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements of curves in the plane - topology, combinatorics, and algorithms. In: Vol 317. Springer; 1988:214-229. doi:10.1007/3-540-19488-6_118
Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., & Sharir, M. (1988). Arrangements of curves in the plane - topology, combinatorics, and algorithms (Vol. 317, pp. 214–229). Presented at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/3-540-19488-6_118
Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms,” 317:214–29. Springer, 1988. https://doi.org/10.1007/3-540-19488-6_118.
H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, “Arrangements of curves in the plane - topology, combinatorics, and algorithms,” presented at the ICALP: Automata, Languages and Programming, 1988, vol. 317, pp. 214–229.
Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1988. Arrangements of curves in the plane - topology, combinatorics, and algorithms. ICALP: Automata, Languages and Programming, LNCS, vol. 317. 214–229.
Edelsbrunner, Herbert, et al. Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms. Vol. 317, Springer, 1988, pp. 214–29, doi:10.1007/3-540-19488-6_118.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar