24 citations · 67 across the 14 of their papers we have counts for
20 papers
From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy
Hsien-Chih Chang, Brittany Terese Fasy, Bradley McCoy +2
Let be a generic closed curve in the plane. Samuel Blank, in his 1967 Ph.D. thesis, determined if is self-overlapping by geometrically constructing a combinatorial word fro…
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. R…
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with tre…
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of…
Near-Linear -Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph (with edge weights) and a subset of terminal vertices, t…
Deterministic, Near-Linear -Approximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra +1
Given point sets and in where and have equal size for some constant dimension and a parameter , we present the first determini…
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…
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…
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…
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…
Efficient Algorithms for Geometric Partial Matching
Pankaj K. Agarwal, Hsien-Chih Chang, Allen Xiao
Let and be two point sets in the plane of sizes and respectively (assume ), and let be a parameter. A matching between and is a family of pair…
Near-Optimal Distance Emulator for Planar Graphs
Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes +1
Given a graph and a set of terminals , a \emph{distance emulator} of is another graph (not necessarily a subgraph of ) containing , such that all the pairwise…
Lower Bounds for Electrical Reduction on Surfaces
Hsien-Chih Chang, Marcos Cossarini, Jeff Erickson
We strengthen the connections between electrical transformations and homotopy from the planar setting---observed and studied since Steinitz---to arbitrary surfaces with punctures.…
Untangling Planar Curves
Hsien-Chih Chang, Jeff Erickson
Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a…
Invertibility and Largest Eigenvalue of Symmetric Matrix Signings
Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang +1
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of ident…
Electrical Reduction, Homotopy Moves, and Defect
Hsien-Chih Chang, Jeff Erickson
We prove the first nontrivial worst-case lower bounds for two closely related problems. First, degree-1 reductions, series-parallel reductions, and Y transformation…
Detecting Weakly Simple Polygons
Hsien-Chih Chang, Jeff Erickson, Chao Xu
A closed curve in the plane is weakly simple if it is the limit (in the Fréchet metric) of a sequence of simple closed curves. We describe an algorithm to determine whether a close…
From Proximity to Utility: A Voronoi Partition of Pareto Optima
Hsien-Chih Chang, Sariel Har-Peled, Benjamin Raichel
We present an extension of Voronoi diagrams where when considering which site a client is going to use, in addition to the site distances, other site attributes are also considered…
A Faster Algorithm to Recognize Even-Hole-Free Graphs
Hsien-Chih Chang, Hsueh-I Lu
We study the problem of determining whether an -node graph has an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoo…
Computing the Girth of a Planar Graph in Linear Time
Hsien-Chih Chang, Hsueh-I Lu
The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an n-node unweighted undirected planar graph. The fir…