Convex decompositions of point sets in the plane

Publication date: 13 September 2019

Abstract: Let

P

be a set of

n

points in general position on the plane. A set of closed convex polygons with vertices in

P

, and with pairwise disjoint interiors is called a convex decomposition of

P

if their union is the convex hull of

P

, and no point of

P

lies in the interior of the polygons. We show that there is a convex decomposition of

P

with at most

f r a c 43 | I (P) | + f r a c 13 | B (P) | + 1 l e f r a c 43 | P | - 2

elements, where

B (P) s u b s e t e q P

is the set of points at the vertices of the convex hull of

P

, and

I (P) = P - B (P)

.

This page was built for publication: Convex decompositions of point sets in the plane