Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#329183] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Van Kreveld, M, Connected component and simple polygon intersection searching, Lecture notes in computer science, vol. 709 LNCS (January, 1993), pp. 37-47, ISBN 9783540571551
    (last updated on 2017/12/15)

    © 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320