Planar point sets divided fairly among agents with few straight lines
Splitting Planar Necklaces with Few Straight Cuts
Computational GeometryData Structures and AlgorithmsComputer Science and Game Theory
Summary
This paper looks at dividing colored points on a flat surface evenly among several people using just a few straight cuts. Normally, dividing colored beads on a line is well known, but this research explores the more complex puzzle of doing it on a plane with straight lines that cut across all points. The authors developed new methods that use fewer lines than previously required, sometimes reducing the number nearly by half compared to simple approaches. They also created efficient algorithms that adapt when points move, keeping divisions fair without many extra cuts.
What this means in practice
- •For robotic path planners: Plan efficient dividing lines to split workspace regions fairly among multiple robots using minimal straight cuts.
- •For data visualization designers: Create clear planar partitions to allocate colored data points fairly across multiple view regions with fewest visual cuts.
Authors
Rishi Advani, Abolfazl Asudeh
Abstract
In the classical necklace splitting problem, beads of different colors lie on a line, and the goal is to divide them among $k$ agents using as few cuts as possible so that every agent receives the same number of beads of each color. We study the planar analog in which a cut is a full straight line and the objective is minimizing the number of lines: $m$ points colored red and blue must be separated by straight-line cuts into regions that can be allocated to $k$ agents so that each agent receives the same number of points of each color. Projection to a line gives $2(k-1)$ cuts, and $k-1$ are sometimes necessary; we give algorithms, static and dynamic, that provably close part of this gap. We develop several approaches that capitalize on the extra degree of freedom: a ``star'' search that produces solutions with as few as $\lceil \frac{k}{2} \rceil$ cuts and never more than $k$ whenever a fair contiguous circular partition exists, with further guarantees for evenly spaced input, and a general algorithm that produces at most $k + \log_2(k+1) - 2$ cuts in $Θ(m \log k)$ time, built on a one-dimensional necklace splitting subroutine that requires no presorting. We then adapt the general algorithm to a dynamic setting, maintaining exact fairness and the cut bound under arbitrary relocation of points, with expected update time that scales with the total distance moved.