2019/10/19 by Eunjin Oh, Oh, Eunjin, Hee-Kap Ahn +1
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotics and Sensor-Based Localization #cs.CG
paper · pdf · doi:10.48550/arxiv.1910.08717
arxiv created 2019/10/19 · openalex publication_date 2019/10/19 · arxiv updated 2019/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the following range searching problem: Preprocess a set P of n points in the plane with respect to a set O of k orientations % , for a constant, in the plane so that given an O-oriented convex polygon Q, the convex hull of P∩ Q can be computed efficiently, where an O-oriented polygon is a polygon whose edges have orientations in O. We present a data structure with O(nk3log2n) space and O(nk3log2n) construction time, and an O(h+slog2 n)-time query algorithm for any query O-oriented convex s-gon Q, where h is the complexity of the convex hull. Also, we can compute the perimeter or area of the convex hull of P∩ Q in O(slog2n) time using the data structure.