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

Math @ Duke



Publications [#329184] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; van Kreveld, M, Implicit point location of line segments, with an arrangements an application to motion planning, Lecture notes in computer science, vol. 652 LNCS (January, 1992), pp. 80-91, ISBN 9783540562870
    (last updated on 2017/12/17)

    © 1992, Springer Verlag. All rights reserved. Let S be a set of n (possibly intersecting) line segments in the plane. We show that tile arrangement of S can be stored implicitly into a data structure of size O(n log 2 n) so that the following query can be answered in time O(n 1/2 log 2 n): Given two query points, determine whether they lie in the same face of the arrangemen t of S and, if so, return a path between them that lies within the face. This version of the implicit point location problem is motivated by the following motion planning problem: Given a polygonal robot R with m vertices and a planar region bounded by polygonal obstacles with n vertices in total, prcprocess them into a data structure so that, glvcn initial and final positions of R, one can quickly dctermine whether there exists a continuous collision-free translational motion of R from the initial to the final position. We show that such a query can be answered in time O((mn) 1/2 log 2 mn) using O(mn log 2 mn) storage.
ph: 919.660.2800
fax: 919.660.2821

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