David Eppstein – Publications

Publications with Benedikt Kolbe

• 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.