Article ID Journal Published Year Pages File Type
414249 Computational Geometry 2015 12 Pages PDF
Abstract

Let P be a set of n points in general position in the plane. In 1996, Urabe considered a partition of P   into subsets S1∪⋯∪SlS1∪⋯∪Sl such that each SiSi forms a hole (or an empty convex polygon) of P   and these holes are mutually disjoint. Let f(P)f(P) be the minimum number of holes over all such partitions of P   and F(n)=max{f(P)}F(n)=max{f(P)} over all sets P of n   points. Then the current best bounds are given by ⌈n+14⌉≤F(n)≤⌈5n18⌉. In this paper, we prove that F(n)≤⌈n4⌉+1.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,