Minimum perimeter-sum partitions in the plane

M. Abrahamsen, M.T. de Berg, K.A. Buchin, M. Mehr, A.D. Mehrabi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P 1 and P 2 such that the sum of the perimeters of CH(P 1) and CH(P 2) is minimized, where CH(P i) denotes the convex hull of P i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n 2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log 4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ 2 · log 4 (1/ϵ)) time.

Original languageEnglish
Title of host publication33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia
EditorsMatthew J. Katz, Boris Aronov
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-15
Number of pages15
ISBN (Electronic)9783959770385
ISBN (Print)978-3-95977-038-5
DOIs
Publication statusPublished - 1 Jun 2017
Event33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017
Conference number: 33
http://socg2017.smp.uq.edu.au/socg.html
http://socg2017.smp.uq.edu.au/index.html

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume77
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Computational Geometry (SoCG 2017)
Abbreviated titleSoCG 2017
CountryAustralia
CityBrisbane
Period4/07/177/07/17
OtherThe Computational Geometry Week (CG Week 2017) is the premier international forum for advances in computational geometry and its many applications. The next edition will take place in Brisbane, Australia, July 4-7, 2017.
CG week combines a number of events, most notably the 33rd International Symposium on Computational Geometry (SoCG 2017), the associated multimedia exposition, workshops, and the Young Researchers Forum.
Internet address

Keywords

  • Clustering
  • Computational geometry
  • Convex hull
  • Minimum-perimeter partition

Fingerprint Dive into the research topics of 'Minimum perimeter-sum partitions in the plane'. Together they form a unique fingerprint.

Cite this