Dynamic planar convex hull operations in near-logarithmic amortized timeDynamic planar convex hull operations in near-logarithmic amortized time

Access Restriction
Subscribed

 Author Chan, Timothy M. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2001 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational geometry ♦ Convex hulls ♦ Dynamic data structures Abstract We give a data structure that allows arbitrary insertions and deletions on a planar point set $\textit{P}$ and supports basic queries on the convex hull of $\textit{P},$ such as membership and tangent-finding. Updates take $\textit{O}(log1+ε\textit{n})$ amori tzed time and queries take $\textit{O}$ (log $\textit{n}$ time each, where $\textit{n}$ is the maximum size of $\textit{P}$ and ε is any fixed positive constant. For some advanced queries such as bridge-finding, both our bounds increase to $\textit{O}(log3/2\textit{n}).$ The only previous fully dynamic solution was by Overmars and van Leeuwen from 1981 and required $\textit{O}(log2\textit{n})$ time per update and $\textit{O}(log$ $\textit{n})$ time per query. 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 2001-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 48 Issue Number 1 Page Count 12 Starting Page 1 Ending Page 12

Open content in new tab

Source: ACM Digital Library