2 Search Results for "Yon, Juyoung"

Document
DOI: 10.4230/LIPIcs.SoCG.2016.63
Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties

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

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

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.
Cite as

Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson. Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yon_et_al:LIPIcs.SoCG.2016.63,
  author =	{Yon, Juyoung and Bae, Sang Won and Cheng, Siu-Wing and Cheong, Otfried and Wilkinson, Bryan T.},
  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 =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.63},
  URN =		{urn:nbn:de:0030-drops-59551},
  doi =		{10.4230/LIPIcs.SoCG.2016.63},
  annote =	{Keywords: shape matching, convexity, symmetric difference, homotheties}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.498
Overlap of Convex Polytopes under Rigid Motion

Authors: Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We present an algorithm to compute an approximate overlap of two convex polytopes P_1 and P_2 in R^3 under rigid motion. Given any epsilon in (0,1/2], our algorithm runs in O(epsilon^{-3}n log^{3.5}n) time with probability 1 - n^{-O(1)} and returns a (1-epsilon)-approximate maximum overlap, provided that the maximum overlap is at least lambda max(|P_1|,|P_2|) for some given constant lambda in (0,1].
Cite as

Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon. Overlap of Convex Polytopes under Rigid Motion. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 498-509, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.FSTTCS.2012.498,
  author =	{Ahn, Hee-Kap and Cheng, Siu-Wing and Kweon, Hyuk Jun and Yon, Juyoung},
  title =	{{Overlap of Convex Polytopes under Rigid Motion}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{498--509},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.498},
  URN =		{urn:nbn:de:0030-drops-38845},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.498},
  annote =	{Keywords: convex polytope, overlap, approximation, rigid motion}
}
  • Refine by Author
  • 2 Cheng, Siu-Wing
  • 2 Yon, Juyoung
  • 1 Ahn, Hee-Kap
  • 1 Bae, Sang Won
  • 1 Cheong, Otfried
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 approximation
  • 1 convex polytope
  • 1 convexity
  • 1 homotheties
  • 1 overlap
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact