Minimum convex partition of a constrained point set

Thomas Fevens, Henk Meijer, David RappaportDiscret. Appl. Math 2001 · OpenReview

Abstract

A convex partition with respect to a point set S is a planar subdivision whose vertices are the points of S, where the boundary of the unbounded outer face is the boundary of the convex hull of S, and every bounded interior face is a convex polygon. A minimum convex partition with respect to S is a convex partition of S such that the number of convex polygons is minimised. In this paper, we will present a polynomial time algorithm to find a minimum convex partition with respect to a point set S where S is constrained to lie on the boundaries of a fixed number of nested convex hulls.
BibTeX
@inproceedings{fevens2001minimum,
  author = {Thomas Fevens and Henk Meijer and David Rappaport},
  title = {{Minimum convex partition of a constrained point set}},
  booktitle = {Discret. Appl. Math},
  year = {2001},
  url = {https://openreview.net/forum?id=kNEOhiMId4},
}

Loading related content...

Figure