Timothy M. Chan
According to our database^{1},
Timothy M. Chan
authored at least 251 papers
between 1994 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org
On csauthors.net:
Bibliography
2019
Approximate shortest paths and distance oracles in weighted unitdisk graphs.
JoCG, 2019
AllPairs Shortest Paths in Geometric Intersection Graphs.
JoCG, 2019
Orthogonal Range Searching in Moderate Dimensions: kd Trees and Range Trees Strike Back.
Discrete & Computational Geometry, 2019
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.
CoRR, 2019
Range closestpair search in higher dimensions.
CoRR, 2019
Dynamic Geometric Data Structures via Shallow Cuttings.
CoRR, 2019
Smallest kEnclosing Rectangle Revisited.
CoRR, 2019
Faster Approximate Diameter and Distance Oracles in Planar Graphs.
Algorithmica, 2019
Two Approaches to Building TimeWindowed Geometric Data Structures.
Algorithmica, 2019
Guarding Orthogonal Art Galleries with Sliding kTransmitters: Hardness and Approximation.
Algorithmica, 2019
Range ClosestPair 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 LocalitySensitive Orderings and Their Applications.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Smallest kEnclosing 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 lowdimensional computational geometry.
JoCG, 2018
An improved approximation algorithm for the discrete Fréchet distance.
Inf. Process. Lett., 2018
On LocalitySensitive Orderings and their Applications.
CoRR, 2018
Stabbing Rectangles by Line Segments  How Decomposition Reduces the ShallowCell Complexity.
CoRR, 2018
Orthogonal Point Location and Rectangle Stabbing Queries in 3d.
CoRR, 2018
Tree Drawings Revisited.
CoRR, 2018
Subquadratic Encodings for Point Configurations.
CoRR, 2018
A ClusteringBased Approach to Kinetic Closest Pair.
Algorithmica, 2018
Approximation Schemes for 01 Knapsack.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018
More LogarithmicFactor Speedups for 3SUM, (median, +)Convolution, and Some Geometric 3SUMHard Problems.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Stabbing Rectangles by Line Segments  How Decomposition Reduces the ShallowCell Complexity.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018
Orthogonal Point Location and Rectangle Stabbing Queries in 3d.
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 UnitDisk 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
InstanceOptimal Geometric Algorithms.
J. ACM, 2017
Improved Bounds for Drawing Trees on Fixed Points with Lshaped 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
AllPairs 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 LShaped 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: kd Trees and Range Trees Strike Back.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017
Applications of Chebyshev Polynomials to LowDimensional 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 2d and 3d Shallow Cuttings.
Discrete & Computational Geometry, 2016
A Simpler LinearTime 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 ClusteringBased 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 RazborovSmolensky.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Improved Deterministic Algorithms for Linear Programming in Low Dimensions.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
AllPairs Shortest Paths in UnitDisk 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 TimeWindowed Geometric Data Structures.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016
Dynamic Streaming Algorithms for EpsilonKernels.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016
2015
Finding median in readonly memory on integer input.
Theor. Comput. Sci., 2015
Drawing Partially Embedded and Simultaneously Planar Graphs.
J. Graph Algorithms Appl., 2015
On Constant Factors in ComparisonBased 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 redblue set cover for unit squares and related problems.
Comput. Geom., 2015
LinearSpace Data Structures for Range Minority Query in Arrays.
Algorithmica, 2015
Clustered Integer 3SUM via Additive Combinatorics.
Proceedings of the FortySeventh Annual ACM on Symposium on Theory of Computing, 2015
Speeding up the Four Russians Algorithm by About One More Logarithmic Factor.
Proceedings of the TwentySixth Annual ACMSIAM 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 2d and 3d Shallow Cuttings.
Proceedings of the 31st International Symposium on Computational Geometry, 2015
A Simpler LinearTime 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
TimeWindowed Closest Pair.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015
2014
LinearSpace Data Structures for Range Mode Query in Arrays.
Theory Comput. Syst., 2014
Maximumweight planar boxes in O(n^{2}) 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 APXhardness 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 TwentyFifth Annual ACMSIAM 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 ComparisonBased 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
SelfApproaching Graphs.
CoRR, 2013
The Art of Shaving Logs.
Proceedings of the Algorithms and Data Structures  13th International Symposium, 2013
SmartGrid 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 TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Morphing Planar Graph Drawings with a Polynomial Number of Steps.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Faster, SpaceEfficient Selection Algorithms in ReadOnly 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 RedBlue Set Cover for Unit Squares and Related Problems.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013
MaximumWeight Planar Boxes in O(n^{2}) Time (and Better).
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013
Quake Heaps: A Simple Alternative to Fibonacci Heaps.
Proceedings of the SpaceEfficient Data Structures, 2013
2012
Allpairs 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 PseudoDisks.
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
LinearSpace Data Structures for Range Minority Query in Arrays.
Proceedings of the Algorithm Theory  SWAT 2012, 2012
LinearSpace 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 quasiuniform sampling.
Proceedings of the TwentyThird Annual ACMSIAM 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
Selfapproaching Graphs.
Proceedings of the Graph Drawing  20th International Symposium, 2012
Conflictfree 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 PseudoDisks
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 NonGeometers: Recent Developments on Some Classical Problems.
Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
Persistent Predecessor Search and Orthogonal point Location on the Word RAM.
Proceedings of the TwentySecond Annual ACMSIAM 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 APXHardness 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 kset problem.
ACM Trans. Algorithms, 2010
Comparisonbased timespace lower bounds for selection.
ACM Trans. Algorithms, 2010
More Algorithms for AllPairs Shortest Paths in Weighted Graphs.
SIAM J. Comput., 2010
A dynamic data structure for 3D convex hulls and 2D nearest neighbor queries.
J. ACM, 2010
Transdichotomous Results in Computational Geometry, II: Offline Search
CoRR, 2010
Optimal inplace and cacheoblivious algorithms for 3d convex hulls and 2d 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 TwentyFirst Annual ACMSIAM 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 hamsandwich cuts in the plane.
Comput. Geom., 2009
An Improved Algorithm for Online Unit Clustering.
Algorithmica, 2009
Dynamic Connectivity for AxisParallel Rectangles.
Algorithmica, 2009
Comparisonbased timespace lower bounds for selection.
Proceedings of the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, 2009
Optimal halfspace range reporting in three dimensions.
Proceedings of the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, 2009
InstanceOptimal Geometric Algorithms.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
Approximation algorithms for maximum independent set of pseudodisks.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009
Optimal inplace algorithms for 3D convex hulls and 2D segment intersection.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009
2008
Wellseparated pair decomposition in linear time?
Inf. Process. Lett., 2008
Dynamic Connectivity: Connecting to Networks and Geometry
CoRR, 2008
AllPairs Shortest Paths with Real Weights in O ( n ^{3}/log n ) Time.
Algorithmica, 2008
Inplace 2d nearest neighbor search.
Proceedings of the Nineteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2008
On the bichromatic kset problem.
Proceedings of the Nineteenth Annual ACMSIAM 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
MultiPass Geometric Algorithms.
Discrete & Computational Geometry, 2007
Voronoi diagrams in n·2^{osqrt(lg lg n)} time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
More algorithms for allpairs 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 coreset constructions and datastream algorithms in fixed dimensions.
Comput. Geom., 2006
Spaceefficient 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 3d convex hulls and 2d nearest neighbor queries.
Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms, 2006
Allpairs shortest paths for unweighted undirected graphs in o(mn) time.
Proceedings of the Seventeenth Annual ACMSIAM 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 AxisParallel 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
LowDimensional 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 vertexorderings of graphs.
Discrete Applied Mathematics, 2005
A note on 3D orthogonal graph drawing.
Discrete Applied Mathematics, 2005
AllPairs Shortest Paths with Real Weights in O(n^{3}/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 ACMSIAM Symposium on Discrete Algorithms, 2005
On levels in arrangements of surfaces in three dimensions.
Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2005
Multipass geometric algorithms.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005
SpaceEfficient Algorithms for Klee's Measure Problem.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
Approximating the piercing number for unitheight rectangles.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
Approximation Algorithms for Maximum Cliques in 3D UnitDisk 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 BoundedDegree Spanning Tree Ratios.
Discrete & Computational Geometry, 2004
FunSortor the chaos of unordered binary search.
Discrete Applied Mathematics, 2004
An optimal randomized algorithm for maximum Tukey depth.
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
SpaceE.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 coreset constructions and data stream algorithms in fixed dimensions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004
Towards inplace geometric algorithms and data structures.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004
2003
SemiOnline Maintenance of Geometric Optima and Measures.
SIAM J. Comput., 2003
Polynomialtime approximation schemes for packing and piercing fat objects.
J. Algorithms, 2003
Drawing K_{2, 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 boundeddegree spanning tree ratios.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003
A SpaceEfficient 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 MinimumWidth Annulus.
Int. J. Comput. Geometry Appl., 2002
Balanced kcolorings.
Discrete Mathematics, 2002
Optimizing area and aspect ration in straightline orthogonal tree drawings.
Comput. Geom., 2002
A NearLinear 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
Semionline maintenance of geometric optima and measures.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Closestpoint problems simplified on the RAM.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
LowDimensional Linear Programming with Violations.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
Drawing k_{2}, 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 nearlogarithmaic 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 kColorings.
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 minimumwidth 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 twocenter algorithms.
Comput. Geom., 1999
A NearLinear Area Bound for Drawing Binary Trees.
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
Dynamic Planar Convex Hull Operations in NearLogarithmic Amortized Time.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
Deterministic Algorithms for 2d Convex Programming and 3d Online Linear Programming.
J. Algorithms, 1998
Backwards Analysis of the KargerKleinTarjan 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: OutputSensitive Construction of FourDimensional Polytopes and ThreeDimensional Voronoi Diagrams.
Discrete & Computational Geometry, 1997
Deterministic Algorithms for 2d Convex Programming and 3d Online Linear Programming.
Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms, 1997
Approximate Nearest Neighbor Queries Revisited.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997
1996
OutputSensitive Results on Convex Hulls, Extreme Points, and Related Problems.
Discrete & Computational Geometry, 1996
Optimal OutputSensitive Convex Hull Algorithms in Two and Three Dimensions.
Discrete & Computational Geometry, 1996
Optimizing Area and Aspect Ratio in StraightLine Orthogonal Tree Drawings.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1996
FixedDimensional Linear Programming Queries Made Easy.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996
1995
OutputSensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three.
Proceedings of the Sixth Annual ACMSIAM Symposium on Discrete Algorithms, 1995
OutputSensitive 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