Math @ Duke

Publications [#329184] of Pankaj K. Agarwal
Papers Published
 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. 8091, ISBN 9783540562870
(last updated on 2017/12/17)
Abstract: © 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 collisionfree 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.


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

