2017/12/01 by Arpita Baral, Abhilash Gondane, Baral, Arpita +5
Computer Science · Engineering · #3D Shape Modeling and Analysis #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1712.00375
arxiv created 2017/12/01 · openalex publication_date 2017/12/01 · arxiv updated 2017/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set P of n points on \mathbb R2, we address the problem of computing an axis-parallel empty rectangular annulus A of maximum-width such that no point of P lies inside A but all points of P must lie inside, outside and on the boundaries of two parallel rectangles forming the annulus A. We propose an O(n3) time and O(n) space algorithm to solve the problem. In a particular case when the inner rectangle of an axis-parallel empty rectangular annulus reduces to an input point we can solve the problem in O(n log n) time and O(n) space.