DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.8

Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions

Authors: Siu-Wing Cheng and Man Ting Wong

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

Abstract

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

Cite as

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

DOI: 10.4230/LIPIcs.SoCG.2020.29

A Generalization of Self-Improving Algorithms

Authors: Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong

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

Abstract

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.

Cite as

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

Search Results

Documents authored by Wong, Man Ting

Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions

Abstract

Cite as

A Generalization of Self-Improving Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message