Source author record

Siu-Wing Cheng

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computational Complexity Information Theory math.IT

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Sparse Signal Recovery from Random Measurements

Given the compressed sensing measurements of an unknown vector $z \in \mathbb{R}^n$ using random matrices, we present a simple method to determine $z$ without solving any optimization problem or linear system. Our method uses $Θ(\log n)$ random sensing matrices in $\mathbb{R}^{k \times n}$ and runs in $O(kn\log n)$ time, where $k = Θ(s\log n)$ and $s$ is the number of nonzero coordinates in $z$ . We adapt our method to determine the support set of $z$ and experimentally compare with some optimization-based methods on binary signals.

preprint2020arXiv

A Generalization of Self-Improving Algorithms

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$ , and the $x_i$ 's are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$ , where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$ , and $H_\mathrm{S}$ and $H_\mathrm{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 \emph{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(\mathrm{poly}(n))$ -time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected running times for sorting and DT, respectively, where $α(\cdot)$ is the inverse Ackermann function.

preprint2020arXiv

Dynamic Distribution-Sensitive Point Location

We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in $\mathbb{R}^2$ , 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 $\cal S$ with $n$ vertices such that each query is answered in $O(\mathrm{OPT})$ expected time, where OPT is the minimum expected time of the best linear decision tree for point location in $\cal S$ . The space and construction time are $O(n\log^2 n)$ . An update of $\cal S$ as a mixed sequence of $k$ edge insertions and deletions takes $O(k\log^5 n)$ amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of $n$ sites can be performed in $O(n\log^5 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.

preprint2015arXiv

Minimax Regret 1-Median Problem in Dynamic Path Networks

This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n^3) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

preprint2014arXiv

A Faster Algorithm for Computing Straight Skeletons

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with $n$ vertices, among which $r$ are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in $O(n (\log n)\log r)$ time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected $O(n \sqrt{h+1}\log^2 n)$ time for a polygon with $h$ holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in $O(n (\log n) \log r + r^{4/3+\varepsilon})$ time for any $\varepsilon>0$ . On degenerate input, our time bound increases to $O(n (\log n) \log r + r^{17/11+\varepsilon})$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.