Follow

Prove that for every n, every polygon (even if it has holes) can be partitioned into n connected pieces of the same area

· · Web · 1 · 2 · 2

@gnivasch
Here is a stack exchange question for this and I had an answer using medial axis.... This is for no holes.. But you can connect the holes so it doesn't matter.
cstheory.stackexchange.com/que

@sarielhp Yeah, it was Erel who asked me the question (I hadn't seen his post). This is the solution Erel and I came up with: If the polygon has holes make some cuts so you get a simple polygon, as you say. Then triangulate the polygon, and connect the triangle centers so you get a tree T. T cuts the polygon into a topological annulus. You can continuously sweep the annulus as in your answer

Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!