24 citations · 67 across the 14 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…
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…