ProbXiv
Explorersign in
Problem archiveProblem record

Statement

(a) Given a map, take the two districts with the largest shared perimeter, then redraw to minimize boundary. Does this process eventually terminate in a simple, Voronoi-like partition (for instance, possibly, the partition minimizing cut edges)? This would imply ergodicity. Or does it get stuck?

(b) Does this policy at least eventually give you a district that is xx-monotone (AKA "vertically convex," no gaps in any vertical slice)? If so, a theorem from the forthcoming paper says that a constant number of steps will suffice to get you to a simple canonical partition, like the Italian flag. This would also prove ergodicity.

(c) How do you efficiently compute the shortest boundary at each step in this process? This might be solved by a paper called. There is a paper that solves this in O(n5)O(n^5) time without the requirement that districts are connected [Papadimitriou and Sideri, 1996].

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.