2013/07/22 by Jatin Agarwal, Agarwal, Jatin, Nadeem Moidu +5
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.1307.5612
This work was previously submitted to IWOCA 2013 and was rejected. The work with better results will appear in proceedings of CCCG 2013
openalex publication_date 2013/07/22 · arxiv created 2013/07/23 · arxiv updated 2013/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of reporting convex hull points in an orthogonal range query in two dimensions. Formally, let P be a set of n points in ℝ2. A point lies on the convex hull of a point set S if it lies on the boundary of the minimum convex polygon formed by S. In this paper, we are interested in finding the points that lie on the boundary of the convex hull of the points in P that also fall with in an orthogonal range[xlt,xrt]×[yb, yt]. We propose a O(n log2 n) space data structure that can support reporting points on a convex hull inside an orthogonal range query, in time O(log3 n + h). Here h is the size of the output. This work improves the result of (Brass et al. 2013) \citebrass that builds a data structure that uses O(n log2 n) space and has a O(log5 n + h) query time. Additionally, we show that our data structure can be modified slightly to solve other related problems. For instance, for counting the number of points on the convex hull in an orthogonal query rectangle, we propose an O(n log2n) space data structure that can be queried upon in O(log3 n) time. We also propose a O(n log2 n) space data structure that can compute the area and perimeter of the convex hull inside an orthogonal range query in O(log3 n) time.