Topologically sweeping an arrangement

H. Edelsbrunner, L. Guibas, Journal of Computer and System Sciences 38 (1989) 165–194.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
Abstract
Sweeping a collection of figures in the Euclidean plane with a straight line is one of the novel algorithmic paradigms that have emerged in the field of computational geometry. In this paper we demonstrate the advantages of sweeping with a topological line that is not necessarily straight. We show how an arrangement of n lines in the plane can be swept over in O(n2) time and O(n) space by a such a line. In the process each element, i.e., vertex, edge, or region, is visited once in a consistent ordering. Our technique makes use of novel data structures which exhibit interesting amortized complexity behavior; the result is an algorithm that improves upon all its predecessors either in the space or the time bounds, as well as being eminently practical. Numerous applications of the technique to problems in computational geometry are given—many through the use of duality transforms. Examples include solving visibility problems, detecting degeneracies in configurations, computing the extremal shadows of convex polytopes, and others. Even though our basic technique solves a planar problem, its applications include several problems in higher dimensions.
Publishing Year
Date Published
1989-02-01
Journal Title
Journal of Computer and System Sciences
Volume
38
Issue
1
Page
165 - 194
IST-REx-ID

Cite this

Edelsbrunner H, Guibas L. Topologically sweeping an arrangement. Journal of Computer and System Sciences. 1989;38(1):165-194. doi:10.1016/0022-0000(89)90038-X
Edelsbrunner, H., & Guibas, L. (1989). Topologically sweeping an arrangement. Journal of Computer and System Sciences, 38(1), 165–194. https://doi.org/10.1016/0022-0000(89)90038-X
Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” Journal of Computer and System Sciences 38, no. 1 (1989): 165–94. https://doi.org/10.1016/0022-0000(89)90038-X.
H. Edelsbrunner and L. Guibas, “Topologically sweeping an arrangement,” Journal of Computer and System Sciences, vol. 38, no. 1, pp. 165–194, 1989.
Edelsbrunner H, Guibas L. 1989. Topologically sweeping an arrangement. Journal of Computer and System Sciences. 38(1), 165–194.
Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” Journal of Computer and System Sciences, vol. 38, no. 1, Elsevier, 1989, pp. 165–94, doi:10.1016/0022-0000(89)90038-X.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar