Source author record

Allen Xiao

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

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Deterministic, Near-Linear $\varepsilon$ -Approximation Algorithm for Geometric Bipartite Matching

Given point sets $A$ and $B$ in $\mathbb{R}^d$ where $A$ and $B$ have equal size $n$ for some constant dimension $d$ and a parameter $\varepsilon>0$ , we present the first deterministic algorithm that computes, in $n\cdot(\varepsilon^{-1} \log n)^{O(d)}$ time, a perfect matching between $A$ and $B$ whose cost is within a $(1+\varepsilon)$ factor of the optimal under any $\smash{\ell_p}$ -norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic $\varepsilon$ -approximation algorithm takes $Ω(n^{3/2})$ time. Our algorithm constructs a (refinement of a) tree cover of $\mathbb{R}^d$ , and we develop several new tools to apply a tree-cover based approach to compute an $\varepsilon$ -approximate perfect matching.

preprint2020arXiv

Dynamic geometric set cover and hitting set

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in $\mathbb{R}^1$ and $\mathbb{R}^2$ . The first framework uses bootstrapping and gives a $(1+\varepsilon)$ -approximate data structure for dynamic interval set cover in $\mathbb{R}^1$ with $O(n^α/\varepsilon)$ amortized update time for any constant $α> 0$ ; in $\mathbb{R}^2$ , this method gives $O(1)$ -approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+α})$ amortized update time. The second framework uses local modification, and leads to a $(1+\varepsilon)$ -approximate data structure for dynamic interval hitting set in $\mathbb{R}^1$ with $\widetilde{O}(1/\varepsilon)$ amortized update time; in $\mathbb{R}^2$ , it gives $O(1)$ -approximate data structures for unit-square (and quadrant) set cover and hitting set in the \textit{partially} dynamic settings with $\widetilde{O}(1)$ amortized update time.

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.

Allen Xiao

Research overview

Is this your work?

2 publications

Deterministic, Near-Linear $\varepsilon$ -Approximation Algorithm for Geometric Bipartite Matching

Dynamic geometric set cover and hitting set

See the researcher in context

Building this map preview

Allen Xiao

Research overview

Is this your work?

2 publications

Deterministic, Near-Linear ε\varepsilonε-Approximation Algorithm for Geometric Bipartite Matching

Dynamic geometric set cover and hitting set

See the researcher in context

Building this map preview

Deterministic, Near-Linear $\varepsilon$ -Approximation Algorithm for Geometric Bipartite Matching