--- res: bibo_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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Herbert foaf_name: Edelsbrunner, Herbert foaf_surname: Edelsbrunner foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-9823-6833 - foaf_Person: foaf_givenName: Leonidas foaf_name: Guibas, Leonidas foaf_surname: Guibas bibo_doi: 10.1016/0022-0000(89)90038-X bibo_issue: '1' bibo_volume: 38 dct_date: 1989^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0022-0000 - http://id.crossref.org/issn/1090-2724 dct_language: eng dct_publisher: Elsevier@ dct_title: Topologically sweeping an arrangement@ ...