Connected component and simple polygon intersection searching
© 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.
Agarwal, PK; Van Kreveld, M
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)