--- _id: '4082' abstract: - lang: eng text: 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. acknowledgement: he authors wish to thank Raimund Seidel for suggesting the argument that we used to prove Theorem 3.1, Harald Rosenberger who implemented the topological sweep and compared it with a straight line sweep, the students who took the Stanford 1985 analysis of algorithms qualifying examination and suffered through a version of this problem, and finally Lyle Ramshaw and Cynthia Hibbard for their detailed reading and comments on the manuscript. The constructive criticism of an anonymous referee is also appreciated. article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Leonidas full_name: Guibas, Leonidas last_name: Guibas citation: ama: 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 apa: Edelsbrunner, H., & Guibas, L. (1989). Topologically sweeping an arrangement. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/0022-0000(89)90038-X chicago: Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” Journal of Computer and System Sciences. Elsevier, 1989. https://doi.org/10.1016/0022-0000(89)90038-X. ieee: H. Edelsbrunner and L. Guibas, “Topologically sweeping an arrangement,” Journal of Computer and System Sciences, vol. 38, no. 1. Elsevier, pp. 165–194, 1989. ista: Edelsbrunner H, Guibas L. 1989. Topologically sweeping an arrangement. Journal of Computer and System Sciences. 38(1), 165–194. mla: 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. short: H. Edelsbrunner, L. Guibas, Journal of Computer and System Sciences 38 (1989) 165–194. date_created: 2018-12-11T12:06:50Z date_published: 1989-02-01T00:00:00Z date_updated: 2022-02-10T16:06:05Z day: '01' doi: 10.1016/0022-0000(89)90038-X extern: '1' intvolume: ' 38' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: https://www.sciencedirect.com/science/article/pii/002200008990038X?via%3Dihub month: '02' oa: 1 oa_version: Published Version page: 165 - 194 publication: Journal of Computer and System Sciences publication_identifier: eissn: - 1090-2724 issn: - 0022-0000 publication_status: published publisher: Elsevier publist_id: '2039' quality_controlled: '1' scopus_import: '1' status: public title: Topologically sweeping an arrangement type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 38 year: '1989' ...