Back to Search
Start Over
Dynamic Convex Hulls under Window-Sliding Updates
- 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