Access Restriction

Author Balstan, Avikam ♦ Sharir, Micha
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The problem of computing the Euclidean shortest path between two points in three-dimensional space bounded by a collection of convex and disjoint polyhedral obstacles having $\textit{n}$ faces altogether is considered. This problem is known to be NP-hard and in exponential time for arbitrarily many obstacles; it can be solved in $\textit{O}(\textit{n}2log$ $\textit{n})$ time for a single convex polyhedral obstacle and in polynomial time for any fixed number of convex obstacles. In this paper Mount's technique is extended to the case of $\textit{two}$ convex polyhedral obstacles and an algorithm that solves this problem in time $\textit{O}(\textit{n}3$ · $2\textit{O}{\textit{α}(\textit{n})4}log$ $\textit{n})$ (where $\textit{α}(\textit{n})$ is the functional inverse of Ackermann's function, and is thus extremely slowly growing) is presented, thus improving significantly Sharir's previous results for this special case. This result is achieved by constructing a new kind of Voronoi diagram, called peeper's Voronoi diagram, which is introduced and analyzed in this paper, and which may be of interest in its own right.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 2
Page Count 21
Starting Page 267
Ending Page 287

Open content in new tab

   Open content in new tab
Source: ACM Digital Library