The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
On Point Location and Motion Planning Among
Marco Pellegrini,
Pages. 1061-1081
Abstract Let $U$ be a set of $n$ possibly intersecting $(d-1)$-simplices in $d$-space for $dgeq 2$, and let $mathcal A(U)$ be the arrangement of $U$. Let $K=mid A(U)mid$ be the number of faces of any dimension in the arrangement of $U$. A data structure is described that uses storage $O(n^{d-1+varepsilon} +K)$ and is built deterministically in time $O(N^{d-1varepsilon}+Klog n)$, where $varepsilon >0$ is an arbitrarily small constant, such that the face of $mathcal A(U)$ containing a query point is located in time $O(log^3 n)$. If two query points are in the same cell of $mathcal A(U)$, a collision-free path connecting them is produced. This result is obtained by exploiting powerful and so far overlooked properties of sparse nets introduced by Chazelle [Discrete Comput. Geom., 9 (1993), pp. 145-158]. If the $(d-1)$-simplices in $U$ have pairwise-disjoint interiors and $dgeq 3$, improved bounds are obtained. A data structure is described that uses $O(n^{d-1})$ storage and is built deterministically in time $O(n^{d-1})$ such that point-location queries are solved in time $O(log n)$. Also, as a by-product, this method gives the first optimal worst-case algorithm for triangulating a nonsimple polyhedron in 3-space.
Contents 1. Introduction
1.1. Point location: definition and previous results
1.2. New results on point location: intersecting simplices
1.3. Motion planning among simplices
1.4. New results in motion planning
1.5. Triangulations
1.6. New results on triangulations
1.7. On cuttings and sparse nets
1.8. The method
2. Spare nets and hierarchical cuttings
3. Incidence and vertical ray-shooting queries
3.1. Preliminary definitions
3.2. A data structure for incidence queries
3.3. The incremental step of the algorithm
3.4. Analysis of the algorithm
3.5. Vertical ray shooting in arrangement of simplices
4. Point location among simplices
4.1. Definitions
4.2. The preprocessing algorithm
4.3. Point-location procedure
4.4. Time and storage analysis
5. A method for building triangulations
5.1. The algorithm
5.2. Analysis of the algorithm
6. Conclusions
Key words rrangements of simplices, point location, sparse nets, motion planning, triangulations.
Mathmatical Subject Classification 68P05, 68Q25, 68Q40, 68U05