Implicit point location of line segments, with an arrangements an application to motion planning


Conference Paper

© 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 log2 n) so that the following query can be answered in time O(n1/2 log2 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 log2 mn) using O(mn log2 mn) storage.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; van Kreveld, M

Published Date

  • January 1, 1992

Published In

Volume / Issue

  • 652 LNCS /

Start / End Page

  • 80 - 91

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540562870

Digital Object Identifier (DOI)

  • 10.1007/3-540-56287-7_96

Citation Source

  • Scopus