The one-local-maximum-per-way conjecture for polygon fillings

About 14 years old · traced to

Let GG be the polygonal domain under consideration, and let M(G)M(G) be its medial axis divided into KK pieces. A way WW is a distribution of NN discs over these pieces, written

W={ni}1K,N=∑iKni,W=\{n_i\}_1^{K},\qquad N=\sum_i^K n_i,

with ni∈Nn_i\in\mathbb{N} and ni∈{0,1}n_i\in\{0,1\} when the ii-th piece is a junction point.

One-local-maximum-per-way conjecture. There is at most one local maximum per way.

If true, an optimal NN-disc filling could be found by generating a maximum for every way; this would reduce the search to a finite collection whose size is of order O(NK−J−1)O\left(N^{K-J-1}\right) when JJ of the KK pieces are junctions. Whether a way can support multiple local maxima is not resolved in the supplied text.

References

Primary source

Carolyn L. Phillips, Joshua A. Anderson, Elizabeth R. Chen and Sharon C. Glotzer, “Optimal Fillings - A new spatial subdivision problem related to packing and covering”, arXiv:1208.5752 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.