DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2023.61

Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation

Authors: Honglin Zhu and Hyuk Jun Kweon

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

Let P be a convex polyhedron and Q be a convex polygon with n vertices in total in three-dimensional space. We present a deterministic algorithm that finds a translation vector v ∈ ℝ³ maximizing the overlap area |P ∩ (Q + v)| in O(n log² n) time. We then apply our algorithm to solve two related problems. We give an O(n log³ n) time algorithm that finds the maximum overlap area of three convex polygons with n vertices in total. We also give an O(n log² n) time algorithm that minimizes the symmetric difference of two convex polygons under scaling and translation.

Cite as

Honglin Zhu and Hyuk Jun Kweon. Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhu_et_al:LIPIcs.SoCG.2023.61,
  author =	{Zhu, Honglin and Kweon, Hyuk Jun},
  title =	{{Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.61},
  URN =		{urn:nbn:de:0030-drops-179116},
  doi =		{10.4230/LIPIcs.SoCG.2023.61},
  annote =	{Keywords: computational geometry, shape matching, arrangement}
}

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}
}

Search Results

Documents authored by Kweon, Hyuk Jun

Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation

Abstract

Cite as

Overlap of Convex Polytopes under Rigid Motion

Abstract

Cite as

Thanks for your feedback!

Could not send message