Connected Component and Simple Polygon Intersection Searching
Published
Journal Article
Efficient data structures are given for the following two query problems: (i) preprocess a set P of simple polygons with a total of n edges, so that all polygons of P intersected by a query segment can be reported efficiently, and (ii) preprocess a set S of n segments, so that the connected components of the arrangement of S intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of size O(n1+f) that can answer a query in time O(n1/2+f + k), where k is the output size. If the edges of P (or the segments in S) are orthogonal, the query time can be improved to O(log n + k) using O(n log n) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time are O(n1/2+f) and O(n1/2+f + k), respectively, and the space used by the data structure is O(n1+f). If we allow O (n4/3+f) space, the amortized update and query time can be improved to O(n1/3+f) and O(n1/3+f + k), respectively. For orthogonal segments the amortized update and query time are O(log2 n) and O(log2 n + k log n), and the space used by the data structure is O(n log n). Some other related results are also mentioned.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Van Kreveld, M
Published Date
- January 1, 1996
Published In
Volume / Issue
- 15 / 6
Start / End Page
- 626 - 660
International Standard Serial Number (ISSN)
- 0178-4617
Digital Object Identifier (DOI)
- 10.1007/BF01940884
Citation Source
- Scopus