Connected component and simple polygon intersection searching


Conference Paper

© Springer-Verlag Berlin Heidelberg 1993. 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 both cases the data structure should return the labels of the intersected polygons or components, not their complete description. Efficient data structures are presented for the static case, the dynamic case, and an efficient on-line construction algorithm for the connected components is given.

Duke Authors

Cited Authors

  • Agarwal, PK; Van Kreveld, M

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 709 LNCS /

Start / End Page

  • 37 - 47

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540571551

Citation Source

  • Scopus