Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414249 | Computational Geometry | 2015 | 12 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kiyoshi Hosono,