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

Follow

@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
Mastodon

Server run by the main developers of the project 🐘 It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!