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.
BibTeX - Entry
@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/opus/volltexte/2023/17911},
URN = {urn:nbn:de:0030-drops-179116},
doi = {10.4230/LIPIcs.SoCG.2023.61},
annote = {Keywords: computational geometry, shape matching, arrangement}
}
|
Keywords: |
|
computational geometry, shape matching, arrangement |
|
Collection: |
|
39th International Symposium on Computational Geometry (SoCG 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
09.06.2023 |
Creative Commons Attribution 4.0 International license (CC BY 4.0)