2023/05/14 by Haitao Wang, Wang, Haitao · 1 citation
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2305.08055
openalex publication_date 2023/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.