Minimum perimeter-sum partitions in the plane

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Titel33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia
RedacteurenMatthew J. Katz, Boris Aronov
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's1-15
Aantal pagina's15
ISBN van elektronische versie9783959770385
ISBN van geprinte versie978-3-95977-038-5
DOI's
StatusGepubliceerd - 1 jun 2017
Evenement33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australië
Duur: 4 jul 20177 jul 2017
Congresnummer: 33
http://socg2017.smp.uq.edu.au/socg.html
http://socg2017.smp.uq.edu.au/index.html

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume77
ISSN van geprinte versie1868-8969

Congres

Congres33rd International Symposium on Computational Geometry (SoCG 2017)
Verkorte titelSoCG 2017
LandAustralië
StadBrisbane
Periode4/07/177/07/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Minimum perimeter-sum partitions in the plane'. Samen vormen ze een unieke vingerafdruk.

Citeer dit