Math @ Duke

Publications [#329183] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Van Kreveld, M, Connected component and simple polygon intersection searching,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS
(January, 1993),
pp. 3747, ISBN 9783540571551
(last updated on 2018/10/16)
Abstract: © SpringerVerlag 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 online construction algorithm for the connected components is given.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

