research-article

Fast fencing

Authors:

Mikkel Abrahamsen,

Anna Adamaszek,

Karl Bringmann,

Vincent Cohen-Addad,

Mikkel ThorupAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 564 - 573

https://doi.org/10.1145/3188745.3188878

Published: 20 June 2018 Publication History

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 polynomialin bothn andk. For the variant with unit cost per curve, or unit disks, we presenta near-linear time algorithm.

Capoyleas, Rote, and Woeginger solved the problem with at most k curves in n^O(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.

Supplementary Material

MP4 File (4c-3.mp4)

Download
28.62 MB

References

[1]

Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup. 2018. Fast Fencing. CoRR abs/1804.00101 (2018).

[2]

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. 2017. Minimum perimeter-sum partitions in the plane. In Proceedings of the 33rd International Symposium on Computational Geometry. 4:1–4:15.

[3]

Pankaj K. Agarwal and Micha Sharir. 1998. Efficient algorithms for geometric optimization. Comput. Surveys 30, 4 (1998), 412–458.

Digital Library

[4]

Esther M. Arkin, Samir Khuller, and Joseph S. B. Mitchell. 1993.

[5]

Geometric knapsack problems. Algorithmica 10, 5 (1993), 399–427.

Digital Library

[6]

Babak Behsaz and Mohammad R. Salavatipour. 2015. On minimum sum of radii and diameters clustering. Algorithmica 73, 1 (2015), 143–165.

Digital Library

[7]

Vasilis Capoyleas, Günter Rote, and Gerhard Woeginger. 1991. Geometric clusterings. Journal of Algorithms 12, 2 (1991), 341–356.

Digital Library

[8]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Cheong. 2008.

[9]

Computational geometry: algorithms and applications (3rd edition). Springer-Verlag.

Digital Library

[10]

Stephen G. Dicke and Britt Hubbard. 2008. Tree protection standards in construction sites. (2008).

[11]

The Forest and Wildlife Research Center, Mississippi State University Extension Service, http://fwrc.msstate.edu/pubs/treeprotection.pdf.

[12]

Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan. 2012.

[13]

On clustering to minimize the sum of radii. SIAM J. Comput. 41, 1 (2012), 47–60.

Digital Library

[14]

Sariel Har-Peled. 2011.

[15]

Geometric approximation algorithms. Vol. 173. American Mathematical Society.

[16]

Joseph S. B. Mitchell. 2017. Private communication. (2017).

Cited By

Ramos NCano Rde Rezende Pde Souza C(2024)Exact and heuristic solutions for the prize‐collecting geometric enclosure problemInternational Transactions in Operational Research10.1111/itor.1342831:4(2093-2122)Online publication date: 13-Jan-2024
https://doi.org/10.1111/itor.13428
Abrahamsen MGiannopoulos PLöffler MRote G(2020)Geometric Multicut: Shortest Fences for Separating Groups of Objects in the PlaneDiscrete & Computational Geometry10.1007/s00454-020-00232-wOnline publication date: 11-Aug-2020
https://doi.org/10.1007/s00454-020-00232-w
Abrahamsen Mde Berg MBuchin KMehr MMehrabi A(2019)Minimum Perimeter-Sum Partitions in the PlaneDiscrete & Computational Geometry10.1007/s00454-019-00059-0Online publication date: 6-Feb-2019
https://doi.org/10.1007/s00454-019-00059-0

Index Terms

Fast fencing
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Fast tate pairing computation on twisted Jacobi intersections curves
Inscrypt'11: Proceedings of the 7th international conference on Information Security and Cryptology

Recently there are lots of studies on the Tate pairing computation with different coordinate systems, such as twisted Edwards curves and Hessian curves coordinate systems. However, Jacobi intersections curves coordinate system, as another useful one, is ...
Families of Fast Elliptic Curves from ℚ-curves
Part I of the Proceedings of the 19th International Conference on Advances in Cryptology - ASIACRYPT 2013 - Volume 8269

We construct new families of elliptic curves over $\mathbb{F}_{p^2}$ with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant---Lambert---Vanstone GLV and Galbraith---Lin---Scott GLS ...
Fast evaluation of derivatives of Bézier curves
Abstract
New geometric methods for fast evaluation of derivatives of polynomial and rational Bézier curves are proposed. They apply an algorithm for evaluating polynomial or rational Bézier curves, which was recently given by the authors. Numerical tests ...
Highlights
- New geometric methods for fast evaluation of derivatives of polynomial and rational Bézier curves are proposed.
- They apply an algorithm for evaluating polynomial or rational Bézier curves, which was recently given by the authors.
- ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Villum Fonden
H2020 Marie SkBodowska-Curie Actions
Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Det Frie Forskningsråd

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
349
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ramos NCano Rde Rezende Pde Souza C(2024)Exact and heuristic solutions for the prize‐collecting geometric enclosure problemInternational Transactions in Operational Research10.1111/itor.1342831:4(2093-2122)Online publication date: 13-Jan-2024
https://doi.org/10.1111/itor.13428
Abrahamsen MGiannopoulos PLöffler MRote G(2020)Geometric Multicut: Shortest Fences for Separating Groups of Objects in the PlaneDiscrete & Computational Geometry10.1007/s00454-020-00232-wOnline publication date: 11-Aug-2020
https://doi.org/10.1007/s00454-020-00232-w
Abrahamsen Mde Berg MBuchin KMehr MMehrabi A(2019)Minimum Perimeter-Sum Partitions in the PlaneDiscrete & Computational Geometry10.1007/s00454-019-00059-0Online publication date: 6-Feb-2019
https://doi.org/10.1007/s00454-019-00059-0

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents