Partitions of planar point sets into polygons

2016/05/18 by Ajit Arvind Diwan, Diwan, Ajit Arvind, Bodhayan Roy +1
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.1605.05546

arxiv created 2016/05/18 · arxiv updated 2016/05/19

Abstract

In this paper, we characterize planar point sets that can be partitioned into disjoint polygons of arbitrarily specified sizes. We provide an algorithm to construct such a partition, if it exists, in polynomial time. We show that this problem is equivalent to finding a specified 2-factor in the visibility graph of the point set. The characterization for the case where all cycles have length 3 also translates to finding a K₃-factor of the visibility graph of the point set. We show that the generalized problem of finding a K_k-factor of the visibility graph of a given point set for k ≥ 5 is NP-hard.

Related

• Minimum Star Partitions of Simple Polygons in Polynomial Time
• Partitioning a Polygon Into Small Pieces
• Minimum Partition of Polygons under Width and Cut Constraints
• Detecting all regular polygons in a point set
• 'Congruent Partitions' of Polygons - a Short Introduction