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:** Dagstuhl Reports, Volume 13, Issue 5 (2023)

This report documents the program and the outcomes of the Dagstuhl Seminar 23221 "Computational Geometry". The seminar was held from May 29th to June 2nd, 2023, and 39 participants from various countries attended it, including two remote participants. Recent advances in computational geometry were presented and discussed, and new challenges were identified. This report collects the abstracts of the talks and the open problems presented at the seminar.

Siu-Wing Cheng, Maarten Löffler, Jeff M. Phillips, and Aleksandr Popov. Computational Geometry (Dagstuhl Seminar 23221). In Dagstuhl Reports, Volume 13, Issue 5, pp. 165-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.13.5.165, author = {Cheng, Siu-Wing and L\"{o}ffler, Maarten and Phillips, Jeff M. and Popov, Aleksandr}, title = {{Computational Geometry (Dagstuhl Seminar 23221)}}, pages = {165--181}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {5}, editor = {Cheng, Siu-Wing and L\"{o}ffler, Maarten and Phillips, Jeff M. and Popov, Aleksandr}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.165}, URN = {urn:nbn:de:0030-drops-193692}, doi = {10.4230/DagRep.13.5.165}, annote = {Keywords: Algorithms, Combinatorics, Geometric Computing, Reconfiguration, Uncertainty} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

We propose κ-approximate nearest neighbor (ANN) data structures for n polygonal curves under the Fréchet distance in ℝ^d, where κ ∈ {1+ε,3+ε} and d ≥ 2. We assume that every input curve has at most m vertices, every query curve has at most k vertices, k ≪ m, and k is given for preprocessing. The query times are Õ(k(mn)^{0.5+ε}/ε^d+ k(d/ε)^O(dk)) for (1+ε)-ANN and Õ(k(mn)^{0.5+ε}/ε^d) for (3+ε)-ANN. The space and expected preprocessing time are Õ(k(mnd^d/ε^d)^O(k+1/ε²)) in both cases. In two and three dimensions, we improve the query times to O(1/ε)^O(k) ⋅ Õ(k) for (1+ε)-ANN and Õ(k) for (3+ε)-ANN. The space and expected preprocessing time improve to O(mn/ε)^O(k) ⋅ Õ(k) in both cases. For ease of presentation, we treat factors in our bounds that depend purely on d as O(1). The hidden polylog factors in the big-Õ notation have powers dependent on d.

Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2023.40, author = {Cheng, Siu-Wing and Huang, Haoqiang}, title = {{Approximate Nearest Neighbor for Polygonal Curves Under Fr\'{e}chet Distance}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {40:1--40:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.40}, URN = {urn:nbn:de:0030-drops-180929}, doi = {10.4230/LIPIcs.ICALP.2023.40}, annote = {Keywords: Polygonal curves, Fr\'{e}chet distance, approximate nearest neighbor} }

Document

**Published in:** LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The n input points are drawn from a hidden mixture of product distributions; we are only given an upper bound m = o(√n) on the number of distributions in the mixture, and the property that for each distribution, an input instance is drawn from it with a probability of Ω(1/n). For any ε ∈ (0,1), after spending O(mn log^O(1)(mn) + m^ε n^(1+ε) log(mn)) time in a training phase, our algorithm achieves an O(1/ε n log m + 1/ε n 2^O(log^* n) + 1/ε H) expected running time with probability at least 1 - O(1/n), where H is the entropy of the distribution of the Voronoi diagram output. The expectation is taken over the input distribution and the randomized decisions of the algorithm. For the Euclidean metric, the expected running time improves to O(1/ε n log m + 1/ε H).

Siu-Wing Cheng and Man Ting Wong. Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ISAAC.2021.8, author = {Cheng, Siu-Wing and Wong, Man Ting}, title = {{Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.8}, URN = {urn:nbn:de:0030-drops-154418}, doi = {10.4230/LIPIcs.ISAAC.2021.8}, annote = {Keywords: entropy, Voronoi diagram, convex distance function, hidden mixture of product distributions} }

Document

**Published in:** Dagstuhl Reports, Volume 11, Issue 4 (2021)

This report documents the program and the outcomes of Dagstuhl Seminar 21181 "Computational Geometry". The seminar was held from May 2 to May 7, 2021. Because of COVID, the seminar was held online in a virtual manner, and 36 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.

Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips. Computational Geometry (Dagstuhl Seminar 21181). In Dagstuhl Reports, Volume 11, Issue 4, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.11.4.1, author = {Cheng, Siu-Wing and Driemel, Anne and Phillips, Jeff M.}, title = {{Computational Geometry (Dagstuhl Seminar 21181)}}, pages = {1--19}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {4}, editor = {Cheng, Siu-Wing and Driemel, Anne 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/DagRep.11.4.1}, URN = {urn:nbn:de:0030-drops-147963}, doi = {10.4230/DagRep.11.4.1}, annote = {Keywords: algorithms, computational geometry, Computational topology, data structures, Discrete geometry} }

Document

Complete Volume

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

LIPIcs, Volume 181, ISAAC 2020, Complete Volume

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 1-1012, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cao_et_al:LIPIcs.ISAAC.2020, title = {{LIPIcs, Volume 181, ISAAC 2020, Complete Volume}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {1--1012}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020}, URN = {urn:nbn:de:0030-drops-133439}, doi = {10.4230/LIPIcs.ISAAC.2020}, annote = {Keywords: LIPIcs, Volume 181, ISAAC 2020, Complete Volume} }

Document

Front Matter

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Front Matter, Table of Contents, Preface, Conference Organization

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2020.0, author = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {0:i--0:xviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.0}, URN = {urn:nbn:de:0030-drops-133448}, doi = {10.4230/LIPIcs.ISAAC.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }

Document

**Published in:** LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x₁,⋯,x_n follow some unknown product distribution. That is, x_i comes from a fixed unknown distribution 𝒟_i, and the x_i’s are drawn independently. After spending O(n^{1+ε}) time in a learning phase, the subsequent expected running time is O((n+ H)/ε), where H ∈ {H_S,H_DT}, and H_S and H_DT are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the x_i’s under the group product distribution. There is a hidden partition of [1,n] into groups; the x_i’s in the k-th group are fixed unknown functions of the same hidden variable u_k; and the u_k’s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map u_k to x_i’s are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + H_S) and O(nα(n) + H_DT) expected running times for sorting and DT, respectively, where α(⋅) is the inverse Ackermann function.

Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong. A Generalization of Self-Improving Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.29, author = {Cheng, Siu-Wing and Chiu, Man-Kwun and Jin, Kai and Wong, Man Ting}, title = {{A Generalization of Self-Improving Algorithms}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.29}, URN = {urn:nbn:de:0030-drops-121873}, doi = {10.4230/LIPIcs.SoCG.2020.29}, annote = {Keywords: expected running time, entropy, sorting, Delaunay triangulation} }

Document

**Published in:** LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in ℝ², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(n log² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(k log⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.

Siu-Wing Cheng and Man-Kit Lau. Dynamic Distribution-Sensitive Point Location. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.30, author = {Cheng, Siu-Wing and Lau, Man-Kit}, title = {{Dynamic Distribution-Sensitive Point Location}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {30:1--30:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.30}, URN = {urn:nbn:de:0030-drops-121882}, doi = {10.4230/LIPIcs.SoCG.2020.30}, annote = {Keywords: dynamic planar point location, convex subdivision, linear decision tree} }

Document

**Published in:** Dagstuhl Reports, Volume 9, Issue 4 (2019)

This report documents the program and the outcomes of Dagstuhl Seminar 19181 "Computational Geometry". The seminar was held from April 28 to May 3, 2019 and 40 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.

Siu-Wing Cheng, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 19181). In Dagstuhl Reports, Volume 9, Issue 4, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.9.4.107, author = {Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff}, title = {{Computational Geometry (Dagstuhl Seminar 19181)}}, pages = {107--123}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {4}, editor = {Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.4.107}, URN = {urn:nbn:de:0030-drops-113064}, doi = {10.4230/DagRep.9.4.107}, annote = {Keywords: Computational geometry, polynomial partition, geometric data structures, approximation} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most 4. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a (6 + delta)-approximation algorithm where delta can be any positive constant, and there is still a gap of roughly 2. In this paper, we narrow the gap significantly by proposing a (4+delta)-approximation algorithm where delta can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is poly(m,n)* n^{poly(1/(delta))} where n is the number of players and m is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to 3 + 21/26 =~ 3.808.

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Allocation: Approximation and Integrality Gap. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2019.38, author = {Cheng, Siu-Wing and Mao, Yuchen}, title = {{Restricted Max-Min Allocation: Approximation and Integrality Gap}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {38:1--38:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.38}, URN = {urn:nbn:de:0030-drops-106143}, doi = {10.4230/LIPIcs.ICALP.2019.38}, annote = {Keywords: fair allocation, configuration LP, approximation, integrality gap} }

Document

**Published in:** LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Ailon et al. (SICOMP 2011) proposed a self-improving sorter that tunes its performance to the unknown input distribution in a training phase. The distribution of the input numbers x_1,x_2,...,x_n must be of the product type, that is, each x_i is drawn independently from an arbitrary distribution D_i, and the D_i's are independent of each other. We study two extensions that relax this requirement. The first extension models hidden classes in the input. We consider the case that numbers in the same class are governed by linear functions of the same hidden random parameter. The second extension considers a hidden mixture of product distributions.

Siu-Wing Cheng and Lie Yan. Extensions of Self-Improving Sorters. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 63:1-63:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ISAAC.2018.63, author = {Cheng, Siu-Wing and Yan, Lie}, title = {{Extensions of Self-Improving Sorters}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {63:1--63:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.63}, URN = {urn:nbn:de:0030-drops-100111}, doi = {10.4230/LIPIcs.ISAAC.2018.63}, annote = {Keywords: sorting, self-improving algorithms, entropy} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: 4+delta for estimation and 6 + 2 sqrt{10} + delta ~~ 12.325 + delta for construction, where delta is an arbitrarily small constant greater than 0. We propose an algorithm that constructs an allocation with value within a factor 6 + delta from the optimum for any constant delta > 0. The running time is polynomial in the input size for any constant delta chosen.

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Fair Allocation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2018.37, author = {Cheng, Siu-Wing and Mao, Yuchen}, title = {{Restricted Max-Min Fair Allocation}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {37:1--37:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.37}, URN = {urn:nbn:de:0030-drops-90418}, doi = {10.4230/LIPIcs.ICALP.2018.37}, annote = {Keywords: Fair allocation, approximation, local search} }

Document

**Published in:** LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

We present a self-adjusting point location structure for convex subdivisions. Let n be the number of vertices in a convex subdivision S. Our structure for S uses O(n) space and processes any online query sequence sigma in O(n + OPT) time, where OPT is the minimum time required by any linear decision tree for answering point location queries in S to process sigma. The O(n + OPT) time bound includes the preprocessing time. Our result is a two-dimensional analog of the static optimality property of splay trees. For connected subdivisions, we achieve a processing time of O(|sigma| log log n + n + OPT).

Siu-Wing Cheng and Man-Kit Lau. Adaptive Planar Point Location. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2017.30, author = {Cheng, Siu-Wing and Lau, Man-Kit}, title = {{Adaptive Planar Point Location}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.30}, URN = {urn:nbn:de:0030-drops-71897}, doi = {10.4230/LIPIcs.SoCG.2017.30}, annote = {Keywords: point location, planar subdivision, static optimality} }

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:** LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

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].

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