TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Sunday, January 03, 2021

Fair Partitions and Voronoi Vertices

 The proof of the Fair Partition/ Spicy Chicken problem begins with weighted Voronoi decompositions of planar convex regions. The friendliest intro to this would be https://www.youtube.com/watch?v=5SfXqTENV_Q&t=11s

The basic thought behind this post: What if we do not allow the Voronoi vertices to have different weights? This is of course, the basic partition of a convex region into Voronoi regions based on a sprinkle of vertices. 

With unweighted Voronoi diagrams we can partition any given convex region C into n convex pieces of equal area (only equal area). Indeed, when the centers are on the same line then the Voronoi parts are strips (planks). Adjusting the centers you may obtain arbitrary widths of the strips. Then using the Knaster--Kuratowski--Mazurkiewicz theorem you may also obtain equal area intersections of the strips with $C$. (this explanation is due to Prof. Roman Karasev).


Further thought:  Is it possible to find a set of n vertices within C that are seeds of an 'unweighted' Voronoi decomposition of C into n convex pieces all of same area and perimeter is achieved? Or maybe a partition so that a finite set of quantities {area, perimeter...} are equal across pieces? For most convex regions, for most n values, there may be no such voronoi vertex sets at all.

Suspicion: One has the feeling that if a set of n interior points exists within C yielding an unweighted voronoi partition into pieces with equal area and perimeter (and maybe a few more such properties) then this point set contains important information about the structure of C.

And further one guesses: if for even some values of n, such a set of points has to exist inside C, then C has to have some special symmetry properties (if such a 'voronoi set' of points exists for all values of n, C might be v special). One might even have some theorem that if a small set of global properties are to be equal over n pieces and a set of unweighted Voronoi vertices exists wihin C to achieve this, then, C might have sufficient symmetry to necessarily require that the pieces will necessarily be congruent to another.

0 Comments:

Post a Comment

<< Home