On the minimum number of mutually disjoint holes in planar point sets
type: Item
instance of: scholarly article
title: On the minimum number of mutually disjoint holes in planar point sets
zbMATH Open document ID: 1331.52024
author: Kiyoshi Hosono
published in: Computational Geometry
publication date: 2016-01-15T00:00:00Z
review text: Let us be given a set \(P\) of \(n\) points in general position in the Euclidean plane. Some \(k\) points of \(P\) make a \(k\)-hole, if they determine a convex \(k\)-gon, not containing any more points from \(P\). Let \(g(P)\) denote the minimum number of holes into which \(P\) can be partitioned, and let \(f(P)\) denote minimum number of holes into which \(P\) can be partitioned such that the convex hulls of the holes are pairwise disjoint. Furthermore, let \(G(n)\) be the maximum of \(g(P)\) for \(|P|=n\), and let \(F(n)\) be the maximum of \(f(P)\) for \(|P|=n\). \textit{M. Urabe} [Discrete Appl. Math. 64, No. 2, 179--191 (1996; Zbl 0849.52015)] started the investigation of these quantities. The paper under review shows \(\lfloor n/4 \rfloor +1\leq G(n)\leq F(n) \leq \lceil n/4\rceil +1\). Even if they are close, these functions are not equal as \(G(11)<F(11)\).
reviewed by: László A. Székely
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 52A10
zbMATH DE Number: 6531079
zbMATH Keywords: partitions of a planar point set
zbMATH Keywords: mutually disjoint holes
zbMATH Keywords: empty convex polygon
MaRDI profile type: Publication
full work available at URL: j.comgeo.2015.07.001
OpenAlex ID: W1193275511
cites work: Forced convex \(n\)-gons in the plane
cites work: Discrete and Computational Geometry
cites work: Q3207683
cites work: Q5759552
cites work: Q3286826
cites work: Empty convex hexagons in planar point sets
cites work: Konvexe Fünfecke in ebenen Punktmengen
cites work: Sets with No Empty Convex 7-Gons
cites work: On the number of disjoint convex quadrilaterals for a planar point set
cites work: Q5628820
cites work: Finding convex sets among points in the plane
cites work: The empty hexagon theorem
cites work: Finding sets of points without empty convex 6-gons
cites work: Q4431229
cites work: Computer solution to the 17-point Erdős-Szekeres problem
cites work: Note on the Erdős-Szekeres theorem
cites work: On a partition into convex polygons
DOI: 10.1016/J.COMGEO.2015.07.001
description: scientific article; zbMATH DE number 6531079