License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.63
URN: urn:nbn:de:0030-drops-59551
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5955/
Go to the corresponding LIPIcs Volume Portal

Yon, Juyoung ; Bae, Sang Won ; Cheng, Siu-Wing ; Cheong, Otfried ; Wilkinson, Bryan T.

Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties

pdf-format:
LIPIcs-SoCG-2016-63.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{yon_et_al:LIPIcs:2016:5955,
  author =	{Juyoung Yon and Sang Won Bae and Siu-Wing Cheng and Otfried Cheong and Bryan T. Wilkinson},
  title =	{{Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5955},
  URN =		{urn:nbn:de:0030-drops-59551},
  doi =		{10.4230/LIPIcs.SoCG.2016.63},
  annote =	{Keywords: shape matching, convexity, symmetric difference, homotheties}
}

Keywords: shape matching, convexity, symmetric difference, homotheties
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI