CODEWITHSUNDEEP
algorithmdynamic-programmingcomputational-geometry
J Yokkie
J Yokkie

Reputation: 21

Minimum Cost Polygon Rectangulation

Given a n*n grid which contains P points, what is the total minimum cost to cover P points using rectangles which must contain exactly K points, cost being the perimeter of rectangles.
1. This problem seems similar to polygon triangulation with an extra constraint being that each small rectangles should contain exactly K number of points.

Upvotes: 1

Views: 369

Answers (1)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

I suspect solving your problem exactly is quite difficult. One possible approach is to use a quad-tree structure, and cease splitting when the next split gets too small with respect to k. Although, as Thomas says in a comment, it is not clear how to achieve exactly k points in each cell.

           

Upvotes: 1

Related Questions