Hsien-Chih Chang

activity

20172022

most citedUntangling Planar Curves

1 citations · 2 across the 3 of their papers we have counts for

collaborators

8 papers

cs.DS2022

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

Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra +1

Given point sets $A$ and $B$ in $R^{d}$ where $A$ and $B$ have equal size $n$ for some constant dimension $d$ and a parameter $ε > 0$ , we present the first determini…

math.GT2021

Hard Diagrams of the Unknot

Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler +5

We present three "hard" diagrams of the unknot. They require (at least) three extra crossings before they can be simplified to the trivial unknot diagram via Reidemeister moves in…

cs.DS2020

Clustering under Perturbation Stability in Near-Linear Time

Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala +2

We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is $α$ -stable if the underlying opti…

math.GT2020★ 1 cited

Tightening Curves on Surfaces Monotonically with Applications

Hsien-Chih Chang, Arnaud de Mesmay

We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number…

cs.CG2020

Dynamic geometric set cover and hitting set

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri +2

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) op…

cs.DS2019

Efficient Algorithms for Geometric Partial Matching

Pankaj K. Agarwal, Hsien-Chih Chang, Allen Xiao

Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$ respectively (assume $r \leq n$ ), and let $k$ be a parameter. A matching between $A$ and $B$ is a family of pair…