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