2 papers
cs.CG2021
Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions
Siu-Wing Cheng, Man Ting Wong
We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The input points are drawn fro…
cs.CG2020
A Generalization of Self-Improving Algorithms
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin +1
Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances follow some unknown \emph{product…