arXiv preprint ·
Splitting Planar Necklaces with Few Straight Cuts
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
CyberHull: Deterministic Malicious URL Isolation via Convex Hull
How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
Coresets for $k$-Means: When Does Uniform Sampling Suffice?
A Bochner Weitzenböck Decomposition for Cellular Sheaf Laplacians, Curvature and Neural Sheaf Diffusion
VisFlow: Interpretable Flow Matching for Visibility Reconstruction, Characterization, and Recognition
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.