Document

**Published in:** LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Let P be a set of at most n points and let R be a set of at most n geometric ranges, such as disks and rectangles, where each p ∈ P has an associated supply s_{p} > 0, and each r ∈ R has an associated demand d_r > 0. A (many-to-many) matching is a set 𝒜 of ordered triples (p,r,a_{pr}) ∈ P × R × ℝ_{> 0} such that p ∈ r and the a_{pr}’s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing ∑_{(p,r,a_{pr}) ∈ 𝒜} a_{pr}.
Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of n red points P and a set of n blue points Q that minimizes the length of the longest edge. For the L_∞-metric, we can do this in time O(n^{1+ε}) in any fixed dimension, for the L₂-metric in the plane in time O(n^{4/3 + ε}), for any ε > 0.

Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric Matching and Bottleneck Problems. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2024.31, author = {Cabello, Sergio and Cheng, Siu-Wing and Cheong, Otfried and Knauer, Christian}, title = {{Geometric Matching and Bottleneck Problems}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {31:1--31:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31}, URN = {urn:nbn:de:0030-drops-199768}, doi = {10.4230/LIPIcs.SoCG.2024.31}, annote = {Keywords: Many-to-many matching, bipartite, planar, geometric, approximation} }

Document

**Published in:** LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

We prove a generalization of Pál's 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360° inside Q. We also prove a lower bound of Omega(m n^{2}) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.

Sang Won Bae, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn, and Sang Duk Yoon. The Reverse Kakeya Problem. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.SoCG.2018.6, author = {Bae, Sang Won and Cabello, Sergio and Cheong, Otfried and Choi, Yoonsung and Stehn, Fabian and Yoon, Sang Duk}, title = {{The Reverse Kakeya Problem}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.6}, URN = {urn:nbn:de:0030-drops-87199}, doi = {10.4230/LIPIcs.SoCG.2018.6}, annote = {Keywords: Kakeya problem, convex, isodynamic point, turning} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

We consider the problem of packing a family of disks 'on a shelf,'
that is, such that each disk touches the x-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in O(n log n) time, and provide an O(n log n)-time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.

Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn. Placing your Coins on a Shelf. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{alt_et_al:LIPIcs.ISAAC.2017.4, author = {Alt, Helmut and Buchin, Kevin and Chaplick, Steven and Cheong, Otfried and Kindermann, Philipp and Knauer, Christian and Stehn, Fabian}, title = {{Placing your Coins on a Shelf}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.4}, URN = {urn:nbn:de:0030-drops-82145}, doi = {10.4230/LIPIcs.ISAAC.2017.4}, annote = {Keywords: packing problems, approximation algorithms, NP-hardness} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized.
We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.

Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, and Christos Levcopoulos. Shortcuts for the Circle. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.ISAAC.2017.9, author = {Bae, Sang Won and de Berg, Mark and Cheong, Otfried and Gudmundsson, Joachim and Levcopoulos, Christos}, title = {{Shortcuts for the Circle}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {9:1--9:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.9}, URN = {urn:nbn:de:0030-drops-82133}, doi = {10.4230/LIPIcs.ISAAC.2017.9}, annote = {Keywords: Computational geometry, graph augmentation problem, circle, shortcut, diameter} }

Document

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

We show that the union of translates of a convex body in three dimensional space can have a cubic number holes in the worst case, where a hole in a set is a connected component of its compliment. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2016.10, author = {Aronov, Boris and Cheong, Otfried and Dobbins, Michael Gene and Goaoc, Xavier}, title = {{The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {10:1--10:16}, 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.10}, URN = {urn:nbn:de:0030-drops-59024}, doi = {10.4230/LIPIcs.SoCG.2016.10}, annote = {Keywords: Union complexity, Convex sets, Motion planning} }

Document

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

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.

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

**Published in:** Dagstuhl Reports, Volume 5, Issue 3 (2015)

This report documents the program and the outcomes of Dagstuhl Seminar 15111 "Computational Geometry". The seminar was held from 8th to 13th March 2015 and 41 senior and young researchers from various countries and continents attended it. Recent developments in the field were presented and new challenges in computational geometry were identified.

Otfried Cheong, Jeff Erickson, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 15111). In Dagstuhl Reports, Volume 5, Issue 3, pp. 41-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.5.3.41, author = {Cheong, Otfried and Erickson, Jeff and Teillaud, Monique}, title = {{Computational Geometry (Dagstuhl Seminar 15111)}}, pages = {41--62}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {5}, number = {3}, editor = {Cheong, Otfried and Erickson, Jeff and Teillaud, Monique}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.41}, URN = {urn:nbn:de:0030-drops-52689}, doi = {10.4230/DagRep.5.3.41}, annote = {Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology} }

Document

**Published in:** Dagstuhl Reports, Volume 3, Issue 3 (2013)

This report documents the program and the outcomes of Dagstuhl Seminar 13101 "Computational Geometry". The seminar was held from 3rd to 8th March 2013 and 47 senior and young researchers from various countries and continents attended it.
Recent developments in the field were presented and new challenges in computational geometry were identified. This report collects abstracts of the talks and a list of open problems.

Otfried Cheong, Kurt Mehlhorn, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 13101). In Dagstuhl Reports, Volume 3, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.3.3.1, author = {Cheong, Otfried and Mehlhorn, Kurt and Teillaud, Monique}, title = {{Computational Geometry (Dagstuhl Seminar 13101)}}, pages = {1--23}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {3}, number = {3}, editor = {Cheong, Otfried and Mehlhorn, Kurt and Teillaud, Monique}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.3.1}, URN = {urn:nbn:de:0030-drops-40210}, doi = {10.4230/DagRep.3.3.1}, annote = {Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology} }