2026-07-20T11:15:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5955 2024-03-06T10:37:21Z ddc:004 open_access

Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties Yon, Juyoung Bae, Sang Won Cheng, Siu-Wing Cheong, Otfried Wilkinson, Bryan T. shape matching convexity symmetric difference homotheties The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juyoung Yon and Sang Won Bae and Siu-Wing Cheng and Otfried Cheong and Bryan T. Wilkinson 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.63 urn:nbn:de:0030-drops-59551 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.63 eng https://creativecommons.org/licenses/by/3.0/legalcode