### Abstract

We consider very natural “fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves, we present an algorithm that is polynomial in both n and k. For the variant with unit cost per curve, or unit disks, we present a near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in nO(k) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k. Our polynomial time algorithm refutes this unless P equals NP.

Original language | English |
---|---|

Title of host publication | Proceedings of 50th Annual ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Publication date | 2018 |

Pages | 1319-1332 |

ISBN (Print) | 9781450355599 |

DOIs | |

Publication status | Published - 2018 |

Event | 50th Annual ACM SIGACT Symposium on Theory of Computing - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 |

### Conference

Conference | 50th Annual ACM SIGACT Symposium on Theory of Computing |
---|---|

Country | United States |

City | Los Angeles |

Period | 25/06/2018 → 29/06/2018 |

Series | Proceedings of the Annual Acm Symposium on Theory of Computing |
---|---|

ISSN | 0737-8017 |

### Keywords

- Geometric clustering
- Minimum perimeter sum

## Cite this

Abrahamsen, M., Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., Roytman, A., & Thorup, M. (2018). Fast fencing. In

*Proceedings of 50th Annual ACM Symposium on Theory of Computing*(pp. 1319-1332). Association for Computing Machinery. Proceedings of the Annual Acm Symposium on Theory of Computing https://doi.org/10.1145/3188745.3188878