Connected Component and Simple Polygon Intersection Searching
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.
Agarwal, PK; Van Kreveld, M
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)