Timothy M. Chan

According to our database1, Timothy M. Chan authored at least 251 papers between 1994 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Approximate shortest paths and distance oracles in weighted unit-disk graphs.
JoCG, 2019

All-Pairs Shortest Paths in Geometric Intersection Graphs.
JoCG, 2019

Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back.
Discrete & Computational Geometry, 2019

Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.
CoRR, 2019

Range closest-pair search in higher dimensions.
CoRR, 2019

Dynamic Geometric Data Structures via Shallow Cuttings.
CoRR, 2019

Smallest k-Enclosing Rectangle Revisited.
CoRR, 2019

Faster Approximate Diameter and Distance Oracles in Planar Graphs.
Algorithmica, 2019

Two Approaches to Building Time-Windowed Geometric Data Structures.
Algorithmica, 2019

Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation.
Algorithmica, 2019

Range Closest-Pair Search in Higher Dimensions.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

On Locality-Sensitive Orderings and Their Applications.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Smallest k-Enclosing Rectangle Revisited.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Dynamic Geometric Data Structures via Shallow Cuttings.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Computing Shapley Values in the Plane.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018
Selection and Sorting in the "Restore" Model.
ACM Trans. Algorithms, 2018

Improved Deterministic Algorithms for Linear Programming in Low Dimensions.
ACM Trans. Algorithms, 2018

Towards an Optimal Method for Dynamic Planar Point Location.
SIAM J. Comput., 2018

Applications of Chebyshev polynomials to low-dimensional computational geometry.
JoCG, 2018

An improved approximation algorithm for the discrete Fréchet distance.
Inf. Process. Lett., 2018

On Locality-Sensitive Orderings and their Applications.
CoRR, 2018

Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity.
CoRR, 2018

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d.
CoRR, 2018

Tree Drawings Revisited.
CoRR, 2018

Subquadratic Encodings for Point Configurations.
CoRR, 2018

A Clustering-Based Approach to Kinetic Closest Pair.
Algorithmica, 2018

Approximation Schemes for 0-1 Knapsack.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

Tree Drawings Revisited.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

Subquadratic Encodings for Point Configurations.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017
How to Morph Planar Graph Drawings.
SIAM J. Comput., 2017

Instance-Optimal Geometric Algorithms.
J. ACM, 2017

Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges.
CoRR, 2017

Dynamic data structures for approximate Hausdorff distance in the word RAM.
Comput. Geom., 2017

Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points.
Comput. Geom., 2017

On the Succinct Representation of Equivalence Classes.
Algorithmica, 2017

Succinct Indices for Path Minimum, with Applications.
Algorithmica, 2017

On Guarding Orthogonal Polygons with Sliding Cameras.
Proceedings of the WALCOM: Algorithms and Computation, 2017

All-Pairs Shortest Paths in Geometric Intersection Graphs.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges.
Proceedings of the Graph Drawing and Network Visualization - 25th International Symposium, 2017

Faster Approximate Diameter and Distance Oracles in Planar Graphs.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Dynamic Orthogonal Range Searching on the RAM, Revisited.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
Adaptive and Approximate Orthogonal Range Counting.
ACM Trans. Algorithms, 2016

Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings.
Discrete & Computational Geometry, 2016

A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions.
Discrete & Computational Geometry, 2016

On Guarding Orthogonal Polygons with Sliding Cameras.
CoRR, 2016

Polynomial Representations of Threshold Functions and Algorithmic Applications.
CoRR, 2016

How to morph planar graph drawings.
CoRR, 2016

A Clustering-Based Approach to Kinetic Closest Pair.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Improved Deterministic Algorithms for Linear Programming in Low Dimensions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Polynomial Representations of Threshold Functions and Algorithmic Applications.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Two Approaches to Building Time-Windowed Geometric Data Structures.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Dynamic Streaming Algorithms for Epsilon-Kernels.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Finding median in read-only memory on integer input.
Theor. Comput. Sci., 2015

Drawing Partially Embedded and Simultaneously Planar Graphs.
J. Graph Algorithms Appl., 2015

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures.
Discrete & Computational Geometry, 2015

Clustered Integer 3SUM via Additive Combinatorics.
CoRR, 2015

Instance Optimal Geometric Algorithms.
CoRR, 2015

Guest Editor's foreword.
Comput. Geom., 2015

Geometric red-blue set cover for unit squares and related problems.
Comput. Geom., 2015

Linear-Space Data Structures for Range Minority Query in Arrays.
Algorithmica, 2015

Clustered Integer 3SUM via Additive Combinatorics.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Speeding up the Four Russians Algorithm by About One More Logarithmic Factor.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Multidimensional Range Selection.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Towards an Optimal Method for Dynamic Planar Point Location.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Fast String Dictionary Lookup with One Error.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

Dynamic data structures for approximate Hausdorff distance in the word RAM.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

Approximating the Minimum Closest Pair Distance and Nearest Neighbor Distances of Linearly Moving Points.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

Time-Windowed Closest Pair.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2014
Linear-Space Data Structures for Range Mode Query in Arrays.
Theory Comput. Syst., 2014

Maximum-weight planar boxes in O(n2) time (and better).
Inf. Process. Lett., 2014

Guest Editors' Foreword.
Discrete & Computational Geometry, 2014

Drawing Partially Embedded and Simultaneously Planar Graphs.
CoRR, 2014

On Hardness of Jumbled Indexing.
CoRR, 2014

Closest pair and the post office problem for stochastic points.
Comput. Geom., 2014

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions.
Comput. Geom., 2014

Exact algorithms and APX-hardness results for geometric packing and covering problems.
Comput. Geom., 2014

Necklaces, Convolutions, and X+Y.
Algorithmica, 2014

Selection and Sorting in the "Restore" Model.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On Hardness of Jumbled Indexing.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Drawing Partially Embedded and Simultaneously Planar Graphs.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

Succinct Indices for Path Minimum, with Applications to Path Reporting.
Proceedings of the Algorithms - ESA 2014, 2014

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Cuttings in 2D Revisited.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014

2013
Persistent Predecessor Search and Orthogonal Point Location on the Word RAM.
ACM Trans. Algorithms, 2013

Self-Approaching Graphs.
CoRR, 2013

The Art of Shaving Logs.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Smart-Grid Electricity Allocation via Strip Packing with Slicing.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Adaptive and Approximate Orthogonal Range Counting.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Morphing Planar Graph Drawings with a Polynomial Number of Steps.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations.
Proceedings of the Graph Drawing - 21st International Symposium, 2013

Klee's Measure Problem Made Easy.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Geometric Red-Blue Set Cover for Unit Squares and Related Problems.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Maximum-Weight Planar Boxes in O(n2) Time (and Better).
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Quake Heaps: A Simple Alternative to Fibonacci Heaps.
Proceedings of the Space-Efficient Data Structures, 2013

2012
All-pairs shortest paths for unweighted undirected graphs in o(mn) time.
ACM Trans. Algorithms, 2012

Three Problems about Dynamic Convex Hulls.
Int. J. Comput. Geometry Appl., 2012

Approximation Algorithms for Maximum Independent Set of Pseudo-Disks.
Discrete & Computational Geometry, 2012

On Levels in Arrangements of Surfaces in Three Dimensions.
Discrete & Computational Geometry, 2012

Optimal Partition Trees.
Discrete & Computational Geometry, 2012

Necklaces, Convolutions, and X+Y
CoRR, 2012

Linear-Space Data Structures for Range Minority Query in Arrays.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

Linear-Space Data Structures for Range Mode Query in Arrays.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Computing the Nearest Neighbor Transform Exactly with Only Double Precision.
Proceedings of the Ninth International Symposium on Voronoi Diagrams in Science and Engineering, 2012

Combinatorial Geometry and Approximation Algorithms.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Self-approaching Graphs.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

2011
Dynamic Connectivity: Connecting to Networks and Geometry.
SIAM J. Comput., 2011

Orthogonal Range Searching on the RAM, Revisited
CoRR, 2011

Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
CoRR, 2011

Closest Pair and the Post Office Problem for Stochastic Points.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Persistent Predecessor Search and Orthogonal point Location on the Word RAM.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Stochastic minimum spanning trees in euclidean spaces.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Orthogonal range searching on the RAM, revisited.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Three problems about dynamic convex hulls.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Exact Algorithms and APX-Hardness Results for Geometric Set Cover.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Bichromatic Line Segment Intersection Counting in O(n sqrt(log n)) Time.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010
On the bichromatic k-set problem.
ACM Trans. Algorithms, 2010

Comparison-based time-space lower bounds for selection.
ACM Trans. Algorithms, 2010

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs.
SIAM J. Comput., 2010

A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries.
J. ACM, 2010

Transdichotomous Results in Computational Geometry, II: Offline Search
CoRR, 2010

Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection.
Comput. Geom., 2010

A (slightly) faster algorithm for Klee's measure problem.
Comput. Geom., 2010

Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Optimal partition trees.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time.
SIAM J. Comput., 2009

A Randomized Algorithm for Online Unit Clustering.
Theory Comput. Syst., 2009

Dynamic Coresets.
Discrete & Computational Geometry, 2009

On Approximate Range Counting and Depth.
Discrete & Computational Geometry, 2009

Dynamic ham-sandwich cuts in the plane.
Comput. Geom., 2009

An Improved Algorithm for Online Unit Clustering.
Algorithmica, 2009

Dynamic Connectivity for Axis-Parallel Rectangles.
Algorithmica, 2009

Comparison-based time-space lower bounds for selection.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Optimal halfspace range reporting in three dimensions.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Instance-Optimal Geometric Algorithms.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Approximation algorithms for maximum independent set of pseudo-disks.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008
Well-separated pair decomposition in linear time?
Inf. Process. Lett., 2008

Dynamic Connectivity: Connecting to Networks and Geometry
CoRR, 2008

All-Pairs Shortest Paths with Real Weights in O ( n 3/log n ) Time.
Algorithmica, 2008

In-place 2-d nearest neighbor search.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On the bichromatic k-set problem.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Dynamic Connectivity: Connecting to Networks and Geometry.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

A (slightly) faster algorithm for klee's measure problem.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

On levels in arrangements of curves, iii: further improvements.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

Dynamic coresets.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Multi-Pass Geometric Algorithms.
Discrete & Computational Geometry, 2007

Voronoi diagrams in n·2osqrt(lg lg n) time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

More algorithms for all-pairs shortest paths in weighted graphs.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

On approximate range counting and depth.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

An Improved Algorithm for Online Unit Clustering.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006
Dynamic Subgraph Connectivity with Geometric Applications.
SIAM J. Comput., 2006

Geometric Optimization Problems over Sliding Windows.
Int. J. Comput. Geometry Appl., 2006

Three problems about simple polygons.
Comput. Geom., 2006

Faster core-set constructions and data-stream algorithms in fixed dimensions.
Comput. Geom., 2006

Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time.
Comput. Geom., 2006

A Randomized Algorithm for Online Unit Clustering.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

All-pairs shortest paths for unweighted undirected graphs in o(mn) time.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Necklaces, Convolutions, and X + Y.
Proceedings of the Algorithms, 2006

Dynamic Connectivity for Axis-Parallel Rectangles.
Proceedings of the Algorithms, 2006

A Simple Streaming Algorithm for Minimum Enclosing Balls.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005
Low-Dimensional Linear Programming with Violations.
SIAM J. Comput., 2005

On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences.
Discrete & Computational Geometry, 2005

Balanced vertex-orderings of graphs.
Discrete Applied Mathematics, 2005

A note on 3D orthogonal graph drawing.
Discrete Applied Mathematics, 2005

All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Finding the shortest bottleneck edge in a parametric minimum spanning tree.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On levels in arrangements of surfaces in three dimensions.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Multi-pass geometric algorithms.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

Space-Efficient Algorithms for Klee's Measure Problem.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Approximating the piercing number for unit-height rectangles.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004
A note on maximum independent sets in rectangle intersection graphs.
Inf. Process. Lett., 2004

Euclidean Bounded-Degree Spanning Tree Ratios.
Discrete & Computational Geometry, 2004

Fun-Sort--or the chaos of unordered binary search.
Discrete Applied Mathematics, 2004

An optimal randomized algorithm for maximum Tukey depth.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Space-E.cient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Geometric Optimization Problems Over Sliding Windows.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Faster core-set constructions and data stream algorithms in fixed dimensions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Towards in-place geometric algorithms and data structures.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003
Semi-Online Maintenance of Geometric Optima and Measures.
SIAM J. Comput., 2003

Polynomial-time approximation schemes for packing and piercing fat objects.
J. Algorithms, 2003

Drawing K2, n: A lower bound.
Inf. Process. Lett., 2003

A Fully Dynamic Algorithm for Planar Width.
Discrete & Computational Geometry, 2003

On Levels in Arrangements of Curves.
Discrete & Computational Geometry, 2003

On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

the asteroid surveying problem and other puzzles.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

Euclidean bounded-degree spanning tree ratios.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

A Space-Efficient Algorithm for Segment Intersection.
Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

Curves of width one and the river shore problem.
Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

2002
Approximating the Diameter, Width, Smallest Enclosing Cylinder, and Minimum-Width Annulus.
Int. J. Comput. Geometry Appl., 2002

Balanced k-colorings.
Discrete Mathematics, 2002

Optimizing area and aspect ration in straight-line orthogonal tree drawings.
Comput. Geom., 2002

A Near-Linear Area Bound for Drawing Binary Trees.
Algorithmica, 2002

Dynamic subgraph connectivity with geometric applications.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Semi-online maintenance of geometric optima and measures.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Closest-point problems simplified on the RAM.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Low-Dimensional Linear Programming with Violations.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Drawing k2, n: A lower bound.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

2001
Fly Cheaply: On the Minimum Fuel Consumption Problem.
J. Algorithms, 2001

Dynamic planar convex hull operations in near-logarithmaic amortized time.
J. ACM, 2001

On Enumerating and Selecting Distances.
Int. J. Comput. Geometry Appl., 2001

A fully dynamic algorithm for planar.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000
Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.
SIAM J. Comput., 2000

Reporting curve segment intersections using restricted predicates.
Comput. Geom., 2000

Balanced k-Colorings.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

On Levels in Arrangements of Curves.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Geometric Applications of a Randomized Optimization Technique.
Discrete & Computational Geometry, 1999

More planar two-center algorithms.
Comput. Geom., 1999

A Near-Linear Area Bound for Drawing Binary Trees.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming.
J. Algorithms, 1998

Backwards Analysis of the Karger-Klein-Tarjan Algorithm for Minimum Spanning Trees.
Inf. Process. Lett., 1998

Approximate Nearest Neighbor Queries Revisited.
Discrete & Computational Geometry, 1998

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%.
Discrete & Computational Geometry, 1998

Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

On Enumerating and Selecting Distances.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

Geometric Applications of a Randomized Optimization Technique.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997
Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams.
Discrete & Computational Geometry, 1997

Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Approximate Nearest Neighbor Queries Revisited.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996
Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems.
Discrete & Computational Geometry, 1996

Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions.
Discrete & Computational Geometry, 1996

Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1996

Fixed-Dimensional Linear Programming Queries Made Easy.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

The complexity of a single face of a minkowski sum.
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

1994
A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections.
Proceedings of the 6th Canadian Conference on Computational Geometry, 1994


  Loading...