Aarhus University Seal

Approximating convex shapes with respect to symmetric difference under homotheties

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



  • Juyoung Yon, Korea Advanced Institute of Science and Technology (KAIST)
  • ,
  • Sang Bae Won, Kyonggi University
  • ,
  • Siu Wing Cheng, Hong Kong University of Science and Technology
  • ,
  • Otfried Cheong, KAIST
  • ,
  • Bryan T. Wilkinson

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)log3(m + n)) expected time, where n and m denote the number of vertices of P and C, respectively.

Original languageEnglish
Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
EditorsSándor Fekete, Anna Lubiw
Number of pages15
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year2016
ISBN (Electronic)9783959770095
Publication statusPublished - 2016
Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
Duration: 14 Jun 201617 Jun 2016


Conference32nd International Symposium on Computational Geometry, SoCG 2016
LandUnited States
Sponsoret al, National Science Foundation (NSF), Princeton University, The Center for Geometry and its Applications (SRC-GAIA), The Fields Institute for Research in Mathematical Sciences, Tufts University
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • Convexity, Homotheties, Shape matching, Symmetric difference

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 109011007