Article ID Journal Published Year Pages File Type
414728 Computational Geometry 2014 9 Pages PDF
Abstract

Let S be a set of n points in the plane in general position, that is, no three points of S   are on a line. We consider an Erdős-type question on the least number hk(n)hk(n) of convex k-holes in S  , and give improved lower bounds on hk(n)hk(n), for 3⩽k⩽53⩽k⩽5. Specifically, we show that h3(n)⩾n2−32n7+227, h4(n)⩾n22−9n4−o(n), and h5(n)⩾3n4−o(n). We further settle several questions on sets of 12 points posed by Dehnhardt in 1987.

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