{"ID":2870195,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.12696","arxiv_id":"2509.12696","title":"Efficient Enumeration of At Most $k$-Out Polygons","abstract":"Let $S$ be a set of $n$ points in the Euclidean plane and general position i.e., no three points are collinear. An \\emph{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 $\\mathcal{O}(n^2 \\log{n})$ delay, while the running time of an existing algorithm is $\\mathcal{O}(n^3 \\log{n})$ delay.","short_abstract":"Let $S$ be a set of $n$ points in the Euclidean plane and general position i.e., no three points are collinear. An \\emph{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...","url_abs":"https://arxiv.org/abs/2509.12696","url_pdf":"https://arxiv.org/pdf/2509.12696v1","authors":"[\"Waseem Akram\",\"Katsuhisa Yamanaka\"]","published":"2025-09-16T05:43:25Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}