Publications with Herman Kaverkort
Bicriteria polygon aggregation with arbitrary shapes.
L. Blank,
D. Eppstein,
J.-H. Haunert,
H. Haverkort,
B. Kolbe,
P. Mayer,
P. Mutzel,
A. Naumann, and
J. Sauer.
arXiv:2507.11212.
We consider a problem of shape aggregation in which we cluster a collection of disjoint regions in the plane by finding a collection of surrounding shapes, covering all the given regions and minimizing a linear combination of area and perimeter. The tradeoff between area and perimeter gives us a nested family of clusterings ranging from each given region forming its own cluster to a single cluster for all the regions. The cluster boundaries are straight line segments and circular arcs, leading to a discretization of the clustering problem that allows its optimal solution to be found in polynomial time by a transformation to network flow.