Timothy M. Chan's Publications

(see also DBLP and Google Scholar; some favorites are highlighted in bold below)

Algorithms, data structures, fine-grained complexity (excluding computational geometry)

Derandomizing pseudopolynomial algorithms for subset sum	SODA'26 | arXiv
Simpler reductions from Exact Triangle (with Yinzhan Xu)	SOSA'24 | arXiv
Faster algorithms for text-to-pattern Hamming distances (with Ce Jin, Virginia Vassilevska Williams, and Yinzhan Xu)	FOCS'24 | arXiv
Fredman's trick meets dominance product: Fine-grained complexity of unweighted APSP, 3SUM counting, and more (with Virginia Vassilevska Williams and Yinzhan Xu)	STOC'23 | arXiv
Hardness for triangle problems under even more believable hypotheses: Reductions from Real APSP, Real 3SUM, and OV (with Virginia Vassilevska Williams and Yinzhan Xu)	STOC'22 | arXiv
All-pairs shortest paths for undirected real-weighted graphs with small additive error	ESA'21 | pdf
Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths (with Virginia Vassilevska Williams and Yinzhan Xu)	ICALP'21 | arXiv
(Near-)linear-time randomized algorithms for row minima in Monge partial matrices and related problems	SODA'21
Near-optimal randomized algorithms for selection in totally monotone matrices	SODA'21
More on change-making and related problems (with Qizheng He)	ESA'20 | JCSS'22 (special issue)
Approximating text-to-pattern Hamming distances (with Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat)	STOC'20 | arXiv
On the change-making problem (with Qizheng He)	SOSA'20
Reducing 3SUM to Convolution-3SUM (with Qizheng He)	SOSA'20 (best paper)
Faster deterministic and Las Vegas algorithms for offline approximate nearest neighbors in high dimensions (with Josh Alman and Ryan Williams)	SODA'20
Approximation schemes for 0-1 knapsack	SOSA'18 | pdf
More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems	SODA'18 | TALG'20 (special issue) | pdf
Faster approximate diameter and distance oracles in planar graphs (with Dimitrios Skrepetos)	ESA'17 | Algorithmica | pdf
On the succinct representation of equivalence classes (with Hicham El-Zein, Moshe Lewenstein, J. Ian Munro, Venkatesh Raman)	Algorithmica'17
Polynomial representations of threshold functions and algorithmic applications (with Josh Alman and Ryan Williams)	FOCS'16 | arXiv | pdf
Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov–Smolensky (with Ryan Williams)	SODA'16 | TALG'21 | pdf | talk slides
Fast string dictionary lookup with one error (with Moshe Lewenstein)	CPM'15 | pdf
Clustered integer 3SUM via additive combinatorics (with Moshe Lewenstein)	STOC'15 | arXiv | talk slides
Speeding up the Four Russians algorithm by about one more logarithmic factor	SODA'15 | pdf | talk slides
Succinct indices for path minimum with applications to path reporting (with Meng He, J. Ian Munro, and Gelin Zhou)	ESA'14 | Algorithmica'17 | pdf
On hardness of jumbled indexing (with Amihood Amir, Moshe Lewenstein, and Noa Lewenstein)	ICALP'14 | arXiv | pdf
Selection and sorting in the "restore" model (with J. Ian Munro and Venkatesh Raman)	SODA'14 | TALG'18
Finding median in read-only memory on integer input (with J. Ian Munro and Venkatesh Raman)	ISAAC'13 | TCS'15
Linear-space data structures for range minority query in arrays (with Stephane Durocher, Matthew Skala, and Bryan T. Wilkinson)	SWAT'12 | Algorithmica'15 | pdf
Linear-space data structures for range mode query in arrays (with Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson)	STACS'12 | TOCS'14 (special issue)
Counting inversions, offline orthogonal range counting, and related problems (with Mihai Pǎtras̜cu)	SODA'10 | pdf
Comparison-based time–space lower bounds for selection	SODA'09 | TALG'10 (special issue) | pdf | talk slides
Dynamic connectivity: Connecting to networks and geometry (with Mihai Patrascu and Liam Roditty)	FOCS'08 | SICOMP'11 | arXiv
More algorithms for all-pairs shortest paths in weighted graphs	STOC'07 | SICOMP'10 | pdf
An improved algorithm for online unit clustering (with Hamid Zarrabi-Zadeh)	COCOON'07 | Algorithmica'09 (special issue)
A randomized algorithm for online unit clustering (with Hamid Zarrabi-Zadeh)	WAOA'06 | TOCS'09 (special issue) | pdf
Necklaces, convolutions, and X + Y (with David Bremner, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pǎtras̜cu, and Perouz Taslakian)	ESA'06 | Algorithmica'14 | arXiv | pdf
All-pairs shortest paths for unweighted undirected graphs in o(mn) time	SODA'06 | TALG'12 | pdf
All-pairs shortest paths with real weights in O(n3/log n) time	WADS'05 | Algorithmica'08 (special issue) | pdf
Finding the shortest bottleneck edge in a parametric minimum spanning tree	SODA'05 (short paper) | pdf
Dynamic subgraph connectivity with geometric applications	STOC'02 | SICOMP'06 | pdf
Balanced k-colorings (with Therese C. Biedl, Erik D. Demaine, Martin Demaine, Rudolf Fleischer, and Ming-wei Wang)	MFCS'00 | DAM'02 | pdf

Computational geometry

Charting the diameter computation landscape of intersection graphs in three dimensions and higher (with Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng)	SoCG'26 | arXiv
Triangulating a polygon with holes in optimal (deterministic) time	SoCG'26 | arXiv
Computing the girth of a segment intersection graph (with Yuancheng Yu)	SoCG'26 | arXiv
Dynamic and streaming algorithms for union volume estimation (with Sujoy Bhore, Karl Bringmann, and Yanheng Wang)	SoCG'26 | arXiv
Delaunay triangulations with predictions (with Sergio Cabello and Panos Giannopoulos)	ITCS'26 | arXiv
Truly subquadratic time algorithms for diameter and related problems in graphs of bounded VC-dimension (with Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng)	FOCS'25 | arXiv
Dynamic streaming algorithms for geometric independent set (with Yuancheng Yu)	WADS'25
A linear time algorithm for maximum overlap of two convex polygons under translation (with Isaac M. Hair)	SoCG'25 (best paper) | arXiv
Sparse bounded hop-spanners for geometric intersection graphs (with Sujoy Bhore, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth)	SoCG'25 | arXiv
Faster algorithms for reverse shortest path in unit-disk graphs and related geometric optimization problems: Improving the shrink-and-bifurcate technique (with Zhengcheng Huang)	SoCG'25 | arXiv
Dynamic independent set of disks (and hypercubes) made easier (with Sujoy Bhore)	SOSA'25
Fast static and dynamic approximation algorithms for geometric optimization problems: Piercing, independent set, vertex cover, and matching (with Sujoy Bhore)	SODA'25 | arXiv
Convex polygon containment: Improving quadratic to near linear time (with Isaac M. Hair)	SoCG'24 | arXiv
Semialgebraic range stabbing, ray shooting, and intersection counting in the plane (with Pingan Cheng and Da Wei Zheng)	SoCG'24 | arXiv
Dynamic geometric connectivity in the plane with constant query time (with Zhengcheng Huang)	SoCG'24 | arXiv
Enclosing points with geometric objects (with Qizheng He and Jie Xue)	SoCG'24 | arXiv
An optimal algorithm for higher-order Voronoi diagrams in the plane: The usefulness of nondeterminism (with Pingan Cheng and Da Wei Zheng)	SODA'24 | arXiv
On the fine-grained complexity of small-size geometric set cover and discrete k-center for small k (with Qizheng He and Yuancheng Yu)	ICALP'24 | arXiv
Constant-hop spanners for more geometric intersection graphs, with even smaller size (with Zhengcheng Huang)	SoCG'23 | arXiv
Minimum L∞ Hausdorff distance of point sets under translation: Generalizing Klee's measure problem	SoCG'23 | arXiv
Finding triangles and other small subgraphs in geometric intersection graphs	SODA'23 | arXiv
Simplex range searching revisited: How to shave logs in multi-level data structures (with Da Wei Zheng)	SODA'23 | arXiv
Hopcroft's problem, log-star shaving, 2D fractional cascading, and decision trees (with Da Wei Zheng)	SODA'22 | TALG'24 (special issue) | arXiv
Dynamic geometric set cover, revisited (with Qizheng He, Subhash Suri, and Jie Xue)	SODA'22 | SICOMP'25 | arXiv
Dynamic colored orthogonal range searching (with Zhengcheng Huang)	ESA'21 | pdf
Faster algorithms for largest empty rectangles and boxes	SoCG'21 | DCG'23 (special issue)
More dynamic data structures for geometric set cover with sublinear update time (with Qizheng He)	SoCG'21 | JoCG'21 (special issue) | arXiv
Simple multi-pass streaming algorithms for skyline points and extreme points (with Saladi Rahul)	STACS'21
Further results on colored range searching (with Qizheng He and Yakov Nekrich)	SoCG'20
Faster approximation algorithms for geometric set cover (with Qizheng He)	SoCG'20
Dynamic generalized closest pair: Revisiting Eppstein's technique	SOSA'20 | pdf
Better data structures for colored orthogonal range reporting (with Yakov Nekrich)	SODA'20 | pdf
Range closest-pair search in higher dimensions (with Saladi Rahul and Jie Xue)	WADS'19 | JoCG'20 | arXiv
Orthogonal range reporting and rectangle stabbing for fat rectangles (with Yakov Nekrich and Michiel Smid)	WADS'19 | arXiv
Computing Shapley values in the plane (with Sergio Cabello)	SoCG'19 | DCG'22 | arXiv
Dynamic geometric data structures via shallow cuttings	SoCG'19 | DCG'20 (special issue) | arXiv
Smallest k-enclosing rectangle revisited (with Sariel Har-Peled)	SoCG'19 | DCG'21 | arXiv
On locality-sensitive orderings and their applications (with Sariel Har-Peled and Mitchell Jones)	ITCS'19 | SICOMP'20
Stabbing rectangles by line segments—how decomposition reduces the shallow-cell complexity (with Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff)	ISAAC'18 | arXiv
Orthogonal point location and rectangle stabbing queries in 3-d (with Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis)	ICALP'18 | JoCG'22
Subquadratic encodings for point configurations (with Jean Cardinal, John Iacono, Stefan Langerman, and Aurélien Ooms)	SoCG'18 | JoCG'19 (special issue) | arXiv
Approximate shortest paths and distance oracles in weighted unit-disk graphs (with Dimitrios Skrepetos)	SoCG'18 | JoCG'19 (special issue) | pdf
Dynamic planar orthogonal point location in sublogarithmic time (with Konstantinos Tsakalidis)	SoCG'18 | pdf
An improved approximation algorithms for the discrete Fréchet distance (with Zahed Rahmati)	IPL'18
All-pairs shortest paths in geometric intersection graphs (with Dimitrios Skrepetos)	WADS'17 | JoCG'19 | pdf
Dynamic orthogonal range searching in the RAM, revisited (with Konstantinos Tsakalidis)	SoCG'17 | JoCG'18 (special issue) | pdf
Applications of Chebyshev polynomials to low-dimensional computational geometry	SoCG'17 | JoCG'18 (special issue) | pdf
Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back	SoCG'17 | DCG'19 (special issue) | pdf
On guarding orthogonal polygons with sliding cameras (with Therese Biedl, Stephanie Lee, Saeed Mehrabi, Fabrizio Montecchiani, and Hamideh Vosoughpour)	WALCOM'17
All-pairs shortest paths in unit disk graphs in slightly subquadratic time (with Dimitrios Skrepetos)	ISAAC'16
A clustering approach to kinetic closest pair (with Zahed Rahmati)	SWAT'16 | Algorithmica'18
Dynamic streaming algorithms for ε-kernels	SoCG'16 | pdf
Two approaches to building time-windowed geometric data structures (with John Hershberger and Simon Pratt)	SoCG'16 | Algorithmica'19 | pdf
Improved deterministic algorithms for linear programming in low dimensions	SODA'16 | TALG'18 (special issue) | pdf
Multidimensional range selection (with Gelin Zhou)	ISAAC'15
Towards an optimal method for dynamic planar point location (with Yakov Nekrich)	FOCS'15 | SICOMP'18 (special issue) | pdf
Time-windowed closest pair (with Simon Pratt)	CCCG'15 | pdf
Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points (with Zahed Rahmati)	CCCG'15 | CGTA'17 (special issue) | pdf
Dynamic data structures for approximate Hausdorff distance in the word RAM (with Dimitrios Skrepetos)	CCCG'15 | CGTA'17 (special issue) | pdf
A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions	SoCG'15 | DCG'16 (special issue) | pdf | talk slides
Optimal deterministic algorithms for 2-d and 3-d shallow cuttings (with Konstantinos Tsakalidis)	SoCG'15 | DCG'16 (special issue) | pdf
Deterministic rectangle enclosure and offline dominance reporting on the RAM (with Peyman Afshani and Konstantinos Tsakalidis)	ICALP'14 | pdf
Better ε-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and ε-kernels (with Sunil Arya)	SoCG'14 | pdf
On constant factors in comparison-based geometric algorithms and data structures (with Patrick Lee)	SoCG'14 | DCG'15 (special issue) | pdf
Minimum length planar embeddings of graphs at fixed vertex locations (with Hella-Franziska Hoffmann, Stephen Kiazyk, and Anna Lubiw)	Graph Drawing'13 | pdf
Klee's measure problem made easy	FOCS'13 | pdf | talk slides
Smart-grid electricity allocation via strip packing with slicing (with Soroush Alamdari, Therese Biedl, Elyot Grant, Krishnam Raju Jampani, S. Keshav, Anna Lubiw, and Vinayak Pathak)	WADS'13 | pdf
Maximum-weight planar boxes in O(n2) time (and better) (with Jérémy Barbay, Gonzalo Navarro, and Pablo Pérez-Lantero)	CCCG'13 | IPL'14 | pdf
Geometric red-blue set cover for unit squares and related problems (with Nan Hu)	CCCG'13 | CGTA'15 (special issue) | pdf
Adaptive and approximate orthogonal range counting (with Bryan T. Wilkinson)	SODA'13 | TALG'16 | pdf
Self-approaching graphs (with Soroush Alamdari, Elyot Grant, Anna Lubiw, and Vinayak Pathak)	Graph Drawing'12 | arXiv | pdf
Computing the nearest neighbor transform exactly with only double precision (with David L. Millman, Steven Love, and Jack Snoeyink)	ISVD'12
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling (with Elyot Grant, Jochen Könemann, and Malcolm Sharpe)	SODA'12 | pdf
Exact algorithms and APX-hardness results for geometric set cover (with Elyot Grant)	CCCG'11 | CGTA'14 (special issue) | pdf
Bichromatic line segment intersection counting in O(n sqrt(log n)) time (with Bryan T. Wilkinson)	CCCG'11 | pdf
Streaming and dynamic algorithms for minimum enclosing balls in high dimensions (with Vinayak Pathak)	WADS'11 | CGTA'14 (special issue) | pdf
Closest pair and the post office problem for stochastic points (with Pegah Kamousi and Subhash Suri)	WADS'11 | CGTA'14 (special issue) | pdf
Orthogonal range searching on the RAM, revisited (with Kasper Green Larsen and Mihai Pǎtras̜cu)	SoCG'11 | arXiv
Three problems about dynamic convex hulls	SoCG'11 | IJCGA'12 | pdf
Stochastic minimum spanning trees in Euclidean spaces (with Pegah Kamousi and Subhash Suri)	SoCG'11 | pdf
Persistent predecessor search and orthogonal point location on the word RAM	SODA'11 | TALG'13 (special issue) | pdf
Optimal partition trees	SoCG'10 | DCG'12 (special issue) | pdf
Instance-optimal geometric algorithms (with Peyman Afshani and Jérémy Barbay)	FOCS'09 | JACM'17 | pdf
Approximation algorithms for maximum independent set of pseudo-disks (with Sariel Har-Peled)	SoCG'09 | DCG'12 | arxiv | pdf
Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection (with Eric Y. Chen)	SoCG'09 | CGTA'10 (special issue) | pdf | talk slides
Optimal halfspace range reporting in three dimensions (with Peyman Afshani)	SODA'09 | pdf
A (slightly) faster algorithm for Klee's measure problem	SoCG'08 | CGTA'10 (special issue) | pdf
Dynamic coresets	SoCG'08 | DCG'09 (special issue) | pdf | talk slides
In-place 2-d nearest neighbor search (with Eric Y. Chen)	SODA'08 | pdf
Well-separated pair decomposition in linear time?	IPL'08 | pdf
Transdichotomous results in computational geometry, II: Offline search (earlier title: Voronoi diagrams in n ⋅ 2sqrt(lg lg n) time) (with Mihai Pǎtras̜cu)	STOC'07 | arXiv
On approximate range counting and depth (with Peyman Afshani)	SoCG'07 | DCG'09 (special issue) | pdf
Three problems about simple polygons	CGTA'06 | pdf
Transdichotomous results in computational geometry, I: Point location in sublogarithmic time (with Mihai Pǎtras̜cu)	FOCS'06 | SICOMP'09 (special issue) | pdf
Dynamic connectivity for axis-parallel rectangles (with Peyman Afshani)	ESA'06 | Algorithmica'09 (special issue) | pdf
A simple streaming algorithm for minimum enclosing balls (with Hamid Zarrabi-Zadeh)	CCCG'06
A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries	SODA'06 | JACM'10 | pdf
Approximating the piercing number for unit-height rectangles (with Abdullah-Al Mahmood)	CCCG'05
Approximation algorithms for maximum cliques in 3D unit-disk graphs (with Peyman Afshani)	CCCG'05
Space-efficient algorithms for Klee's measure problem (with Eric Y. Chen)	CCCG'05
Multi-pass geometric algorithms (with Eric Y. Chen)	SoCG'05 | DCG'07 (special issue) | pdf
Geometric optimization problems over sliding windows (with Bashir S. Sadjad)	ISAAC'04 (best student paper for Bashir) | IJCGA'06 (special issue) | pdf
Faster core-set constructions and data-stream algorithms in fixed dimensions	SoCG'04 | CGTA'06 (special issue) | pdf
Towards in-place geometric algorithms and data structures (with Hervé Brönnimann and Eric Y. Chen)	SoCG'04 | pdf
Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time (with Hervé Brönnimann)	LATIN'04 | CGTA'06 | pdf
An optimal randomized algorithm for maximum Tukey depth	SODA'04 | pdf
A note on maximum independent sets in rectangle intersection graphs	IPL'04 | pdf
A space-efficient algorithm for segment intersection (with Eric Y. Chen)	CCCG'03 | pdf
Curves of width one and the river shore problem (with Alexander Golynski, Alejandro López-Ortiz, and Claude-Guy Quimper)	CCCG'03 | pdf
The asteroid surveying problem and other puzzles (with Alexander Golynski, Alejandro López-Ortiz, and Claude-Guy Quimper)	SoCG'03 (video) | pdf
Euclidean bounded-degree spanning tree ratios	SoCG'03 | DCG'04 (special issue) | pdf
Polynomial-time approximation schemes for packing and piercing fat objects	J. Algorithms'03 | pdf
Low-dimensional linear programming with violations	FOCS'02 | SICOMP'05 | pdf
Closest-point problems simplified on the RAM	SODA'02 (short paper) | pdf
Semi-online maintenance of geometric optima and measures	SODA'02 | SICOMP'03 | pdf
A fully dynamic algorithm for planar width	SoCG'01 | DCG'03 (special issue) | pdf
Fly cheaply: On the minimum fuel consumption problem (with Alon Efrat)	J. Algorithms'01
Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus	SoCG'00 | IJCGA'02 (special issue) | pdf
Reporting curve segment intersections using restricted predicates	CGTA'00 | pdf
Dynamic planar convex hull operations in near-logarithmic amortized time	FOCS'99 | JACM'01 | pdf
More planar two-center algorithms	CGTA'99 | pdf
Random sampling, halfspace range reporting, and construction of (≤ k)-levels in three dimensions	FOCS'98 | SICOMP'00 | pdf
Geometric applications of a randomized optimization technique	SoCG'98 | DCG'99 (special issue) | pdf
On enumerating and selecting distances	SoCG'98 | IJCGA'01 (special issue) | pdf
Approximate nearest neighbor queries revisited	SoCG'97 | DCG'98 (special issue) | pdf
Deterministic algorithms for 2-d convex programming and 3-d online linear programming	SODA'97 | J. Algorithms'98 | pdf
Fixed-dimensional linear programming queries made easy	SoCG'96 | pdf
Optimal output-sensitive convex hull algorithms in two and three dimensions	DCG'96 (split from SoCG'95 paper) | pdf
Output-sensitive results on convex hulls, extreme points, and related problems	SoCG'95 | DCG'96 (special issue) | pdf
Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams (with Jack Snoeyink and Chee-Keng Yap)	SODA'95 | DCG'97 | pdf
A simple trapezoid sweep algorithm for reporting red/blue segment intersections	CCCG'94 | pdf

Combinatorial geometry

On Zarankiewicz's problem for intersection hypergraphs of geometric objects (with Chaya Keller and Shakhar Smorodinsky)	SoCG'25 | arXiv
On the number of incidences when avoiding an induced biclique in geometric settings (with Sariel Har-Peled)	SODA'23 | DCG'25 | arXiv
Improved upper and lower bounds for LR drawings of binary trees (with Zhengcheng Huang)	Graph Drawing'20 | arXiv
Tree drawings revisited	SoCG'18 | DCG'20 (special issue) | arXiv | pdf
Improved bounds for drawing trees on fixed points with L-shaped edges (with Therese Biedl, Martin Derka, Kshitij Jain, and Anna Lubiw)	Graph Drawing'17
Drawing partially embedded and simultaneously planar graphs (with Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, and Marcus Schaefer)	Graph Drawing'14 | JGAA'16 (special issue)
How to morph planar graph drawings (with Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, and Bryan T. Wilkinson)	SODA'13 | SICOMP'17 | arXiv
Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set	SoCG'12 | pdf | talk slides
On levels in arrangements of curves, III: Further improvements	SoCG'08 | pdf | talk slides
On the bichromatic k-set problem	SODA'08 | TALG'10 (special issue) | pdf | talk slides
On levels in arrangements of surfaces in three dimensions	SODA'05 | DCG'12 | pdf
On levels in arrangements of curves, II: A simple inequality and its consequence	FOCS'03 | DCG'05 | pdf
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles (with Therese Biedl, Erik D. Demaine, Martin Demaine, Paul Nijjar, Ryuhei Uehara, and Ming-Wei Wang)	CCCG'02 | pdf
Drawing K2,n: A lower bound (with Therese Biedl and Alejandro López-Ortiz)	CCCG'02 | IPL'02 | pdf
On levels in arrangements of curves	FOCS'00 | DCG'03 | pdf
A near-linear area bound for drawing binary trees	SODA'99 | Algorithmica'02 | pdf
On levels in arrangements of lines, segments, planes, and triangles (with Pankaj K. Agarwal, Boris Aronov, and Micha Sharir)	DCG'98 | pdf
Optimizing area and aspect ratio in straight-line orthogonal tree drawings (with Michael T. Goodrich, S. Rao Kosaraju, and Roberto Tamassia)	Graph Drawing'96 | CGTA'02 | pdf
The complexity of a single face of a Minkowski sum (with Sariel Har-Peled, Boris Aronov, Dan Halperin, and Jack Snoeyink)	CCCG'95 | pdf

Miscellaneous/fun stuff

Quake heaps: A simple alternative to Fibonacci heaps	Ianfest'13 | pdf
A minimalist's implementation of an approximate nearest neighbor algorithm in fixed dimensions	pdf ('06) | C++ code
A minimalist's implementation of the 3-d divide-and-conquer convex hull algorithm	pdf ('03) | C++ code for brute force, gift wrapping, and divide-and-conquer
Fun-sort—or the chaos of unordered binary search (with Therese Biedl, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, and J. Ian Munro)	FUN'01 | DAM'04 | pdf
Remarks on k-level algorithms in the plane	pdf ('99)
Backwards analysis of the Karger–Klein–Tarjan algorithm for minimum spanning trees	IPL'98 | pdf