Back to Search Start Over

Dynamic Convex Hulls under Window-Sliding Updates

Authors :
Wang, Haitao
Wang, Haitao
Publication Year :
2023

Abstract

We consider the problem of dynamically maintaining the convex hull of a set $S$ of points in the plane under the following special sequence of insertions and deletions (called {\em window-sliding updates}): insert a point to the right of all points of $S$ and delete the leftmost point of $S$. We propose an $O(|S|)$-space data structure that can handle each update in $O(1)$ amortized time, such that standard binary-search-based queries on the convex hull of $S$ can be answered in $O(\log h)$ time, where $h$ is the number of vertices of the convex hull of $S$, and the convex hull itself can be output in $O(h)$ time.<br />Comment: A previous version appeared in WADS 2023, where the query time was O(log |S|). This new version improves the query time to O(log h)

Details

Database :
OAIster
Publication Type :
Electronic Resource
Accession number :
edsoai.on1381625266
Document Type :
Electronic Resource