2025/09/16 by Waseem Akram, Akram, Waseem, Katsuhisa Yamanaka +1
Computer Science · Engineering · #3D Modeling in Geospatial Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2509.12696
openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
Let S be a set of n points in the Euclidean plane and general position i.e., no three points are collinear. An at most k-out polygon of S is a simple polygon such that each vertex is a point in S and there are at most k points outside the polygon. In this paper, we consider the problem of enumerating all the at most k-out polygon of S. We propose a new enumeration algorithm for the at most k-out polygons of a point set. Our algorithm enumerates all the at most k-out polygons in O(n2 logn) delay, while the running time of an existing algorithm is O(n3 logn) delay.