Timothy M. Chan

Proceedings of the 41st International Symposium on Computational Geometry, 2025

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation.

[BibT_eX]

[DOI]

Isaac M. Hair

Proceedings of the 41st International Symposium on Computational Geometry, 2025

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Computational Geometry, 2025

2024

Hopcroft's Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, July, 2024

Fully Dynamic Geometric Vertex Cover and Matching.

[BibT_eX]

[DOI]

Sujoy Bhore

CoRR, 2024

Simpler Reductions from Exact Triangle.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism.

[BibT_eX]

[DOI]

Pingan Cheng

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic Geometric Connectivity in the Plane with Constant Query Time.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

Convex Polygon Containment: Improving Quadratic to Near Linear Time.

[BibT_eX]

[DOI]

Isaac M. Hair

Proceedings of the 40th International Symposium on Computational Geometry, 2024

Enclosing Points with Geometric Objects.

[BibT_eX]

[DOI]

Jie Xue

Proceedings of the 40th International Symposium on Computational Geometry, 2024

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane.

[BibT_eX]

[DOI]

Pingan Cheng

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Minimum L∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem.

[BibT_eX]

[DOI]

CoRR, 2023

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k.

[BibT_eX]

[DOI]

Yuancheng Yu

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Faster Algorithms for Text-to-Pattern Hamming Distances.

[BibT_eX]

[DOI]

Ce Jin

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Computational Geometry, 2023

Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Optimal Algorithms for Geometric Centers and Depth.

[BibT_eX]

[DOI]

Mitchell Jones

SIAM J. Comput., 2022

Corrigendum to "Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points" [Comput. Geom. 60 (2017) 2-7].

[BibT_eX]

[DOI]

Comput. Geom., 2022

Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Dynamic Geometric Set Cover, Revisited.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points.

[BibT_eX]

[DOI]

Saladi Rahul

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Dynamic Colored Orthogonal Range Searching.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

Faster Algorithms for Largest Empty Rectangles and Boxes.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Approximating text-to-pattern Hamming distances.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Better Data Structures for Colored Orthogonal Range Reporting.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

On the Change-Making Problem.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Reducing 3SUM to Convolution-3SUM.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions.

[BibT_eX]

[DOI]

Josh Alman

R. Ryan Williams

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Improved Upper and Lower Bounds for LR Drawings of Binary Trees.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 28th International Symposium, 2020

More on Change-Making and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Further Results on Colored Range Searching.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Computational Geometry, 2020

Faster Approximation Algorithms for Geometric Set Cover.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019

Two Approaches to Building Time-Windowed Geometric Data Structures.

[BibT_eX]

[DOI]

John Hershberger

Simon Pratt

Algorithmica, 2019

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

[BibT_eX]

[DOI]

Fabrizio Montecchiani

Hamideh Vosoughpour

Ziting Yu

Algorithmica, 2019

Range Closest-Pair Search in Higher Dimensions.

[BibT_eX]

[DOI]

Saladi Rahul

Jie Xue

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.

[BibT_eX]

[DOI]

Michiel H. M. Smid

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

On Locality-Sensitive Orderings and Their Applications.

[BibT_eX]

[DOI]

Mitchell Jones

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Smallest k-Enclosing Rectangle Revisited.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

Dynamic Geometric Data Structures via Shallow Cuttings.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

Computing Shapley Values in the Plane.

[BibT_eX]

[DOI]

Sergio Cabello

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

An improved approximation algorithm for the discrete Fréchet distance.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2018

Approximation Schemes for 0-1 Knapsack.

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

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

[BibT_eX]

[DOI]

Saladi Rahul

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

Tree Drawings Revisited.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

Subquadratic Encodings for Point Configurations.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

How to Morph Planar Graph Drawings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

On the Succinct Representation of Equivalence Classes.

[BibT_eX]

[DOI]

Algorithmica, 2017

Succinct Indices for Path Minimum, with Applications.

[BibT_eX]

[DOI]

Algorithmica, 2017

On Guarding Orthogonal Polygons with Sliding Cameras.

[BibT_eX]

[DOI]

Fabrizio Montecchiani

Hamideh Vosoughpour

Proceedings of the WALCOM: Algorithms and Computation, 2017

All-Pairs Shortest Paths in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 25th International Symposium, 2017

Faster Approximate Diameter and Distance Oracles in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Dynamic Orthogonal Range Searching on the RAM, Revisited.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

A Clustering-Based Approach to Kinetic Closest Pair.

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky.

[BibT_eX]

[DOI]

Ryan Williams

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Improved Deterministic Algorithms for Linear Programming in Low Dimensions.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Polynomial Representations of Threshold Functions and Algorithmic Applications.

[BibT_eX]

[DOI]

Josh Alman

R. Ryan Williams

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Two Approaches to Building Time-Windowed Geometric Data Structures.

[BibT_eX]

[DOI]

Simon Pratt

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Dynamic Streaming Algorithms for Epsilon-Kernels.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Finding median in read-only memory on integer input.

[BibT_eX]

[DOI]

J. Ian Munro

Venkatesh Raman

Theor. Comput. Sci., 2015

Guest Editor's foreword.

[BibT_eX]

[DOI]

Rolf Klein

Comput. Geom., 2015

Clustered Integer 3SUM via Additive Combinatorics.

[BibT_eX]

[DOI]

Moshe Lewenstein

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.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Multidimensional Range Selection.

[BibT_eX]

[DOI]

Gelin Zhou

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Towards an Optimal Method for Dynamic Planar Point Location.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Fast String Dictionary Lookup with One Error.

[BibT_eX]

[DOI]

Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Computational Geometry, 2015

A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Computational Geometry, 2015

Dynamic data structures for approximate Hausdorff distance in the word RAM.

[BibT_eX]

[DOI]

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

Approximating the Minimum Closest Pair Distance and Nearest Neighbor Distances of Linearly Moving Points.

[BibT_eX]

[DOI]

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

Time-Windowed Closest Pair.

[BibT_eX]

[DOI]

Simon Pratt

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2014

Guest Editors' Foreword.

[BibT_eX]

[DOI]

Rolf Klein

Discret. Comput. Geom., 2014

Exact algorithms and APX-hardness results for geometric packing and covering problems.

[BibT_eX]

[DOI]

Elyot Grant

Comput. Geom., 2014

Necklaces, Convolutions, and X+Y.

[BibT_eX]

[DOI]

Algorithmica, 2014

Selection and Sorting in the "Restore" Model.

[BibT_eX]

[DOI]

J. Ian Munro

Venkatesh Raman

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On Hardness of Jumbled Indexing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Drawing Partially Embedded and Simultaneously Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 22nd International Symposium, 2014

Succinct Indices for Path Minimum, with Applications to Path Reporting.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures.

[BibT_eX]

[DOI]

Patrick Lee

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels.

[BibT_eX]

[DOI]

Sunil Arya

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Cuttings in 2D Revisited.

[BibT_eX]

[DOI]

Proceedings of the 26th Canadian Conference on Computational Geometry, 2014

2013

The Art of Shaving Logs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Smart-Grid Electricity Allocation via Strip Packing with Slicing.

[BibT_eX]

[DOI]

Krishnam Raju Jampani

Srinivasan Keshav

Anna Lubiw

Vinayak Pathak

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Adaptive and Approximate Orthogonal Range Counting.

[BibT_eX]

[DOI]

Bryan T. Wilkinson

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Morphing Planar Graph Drawings with a Polynomial Number of Steps.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers.

[BibT_eX]

[DOI]

J. Ian Munro

Venkatesh Raman

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations.

[BibT_eX]

[DOI]

Hella-Franziska Hoffmann

Stephen Kiazyk

Anna Lubiw

Proceedings of the Graph Drawing - 21st International Symposium, 2013

Klee's Measure Problem Made Easy.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Geometric Red-Blue Set Cover for Unit Squares and Related Problems.

[BibT_eX]

[DOI]

Nan Hu

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Maximum-Weight Planar Boxes in O(n2) Time (and Better).

[BibT_eX]

[DOI]

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Quake Heaps: A Simple Alternative to Fibonacci Heaps.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

All-pairs shortest paths for unweighted undirected graphs in o(mn) time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

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

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Linear-Space Data Structures for Range Mode Query in Arrays.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Computing the Nearest Neighbor Transform Exactly with Only Double Precision.

[BibT_eX]

[DOI]

Proceedings of the Ninth International Symposium on Voronoi Diagrams in Science and Engineering, 2012

Combinatorial Geometry and Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Self-approaching Graphs.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Closest Pair and the Post Office Problem for Stochastic Points.

[BibT_eX]

[DOI]

Pegah Kamousi

Subhash Suri

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions.

[BibT_eX]

[DOI]

Vinayak Pathak

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Persistent Predecessor Search and Orthogonal point Location on the Word RAM.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Stochastic minimum spanning trees in euclidean spaces.

[BibT_eX]

[DOI]

Pegah Kamousi

Subhash Suri

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Orthogonal range searching on the RAM, revisited.

[BibT_eX]

[DOI]

Kasper Green Larsen

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Three problems about dynamic convex hulls.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Exact Algorithms and APX-Hardness Results for Geometric Set Cover.

[BibT_eX]

[DOI]

Elyot Grant

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Bichromatic Line Segment Intersection Counting in O(n sqrt(log n)) Time.

[BibT_eX]

[DOI]

Bryan T. Wilkinson

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Transdichotomous Results in Computational Geometry, II: Offline Search

[BibT_eX]

[DOI]

CoRR, 2010

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

[BibT_eX]

[DOI]

Comput. Geom., 2010

Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Optimal partition trees.

[BibT_eX]

[DOI]

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009

Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Dynamic ham-sandwich cuts in the plane.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Comparison-based time-space lower bounds for selection.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Optimal halfspace range reporting in three dimensions.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Instance-Optimal Geometric Algorithms.

[BibT_eX]

[DOI]

Jérémy Barbay

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Approximation algorithms for maximum independent set of pseudo-disks.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008

Well-separated pair decomposition in linear time?

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

In-place 2-d nearest neighbor search.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On the bichromatic k-set problem.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Dynamic Connectivity: Connecting to Networks and Geometry.

[BibT_eX]

[DOI]

Liam Roditty

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

A (slightly) faster algorithm for klee's measure problem.

[BibT_eX]

[DOI]

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

On levels in arrangements of curves, iii: further improvements.

[BibT_eX]

[DOI]

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

Dynamic coresets.

[BibT_eX]

[DOI]

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

2007

Voronoi diagrams in n·2osqrt(lg lg n) time.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

More algorithms for all-pairs shortest paths in weighted graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

On approximate range counting and depth.

[BibT_eX]

[DOI]

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

An Improved Algorithm for Online Unit Clustering.

[BibT_eX]

[DOI]

Hamid Zarrabi-Zadeh

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Three problems about simple polygons.

[BibT_eX]

[DOI]

Comput. Geom., 2006

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

[BibT_eX]

[DOI]

Hervé Brönnimann

Comput. Geom., 2006

A Randomized Algorithm for Online Unit Clustering.

[BibT_eX]

[DOI]

Hamid Zarrabi-Zadeh

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.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

All-pairs shortest paths for unweighted undirected graphs in o(mn) time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

Necklaces, Convolutions, and X + Y.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

Dynamic Connectivity for Axis-Parallel Rectangles.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

A Simple Streaming Algorithm for Minimum Enclosing Balls.

[BibT_eX]

[DOI]

Hamid Zarrabi-Zadeh

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Balanced vertex-orderings of graphs.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Yashar Ganjali

David R. Wood

Discret. Appl. Math., 2005

A note on 3D orthogonal graph drawing.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Finding the shortest bottleneck edge in a parametric minimum spanning tree.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On levels in arrangements of surfaces in three dimensions.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Multi-pass geometric algorithms.

[BibT_eX]

[DOI]

Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

Space-Efficient Algorithms for Klee's Measure Problem.

[BibT_eX]

[DOI]

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Approximating the piercing number for unit-height rectangles.

[BibT_eX]

[DOI]

Abdullah-Al Mahmood

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004

A note on maximum independent sets in rectangle intersection graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Fun-Sort--or the chaos of unordered binary search.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2004

An optimal randomized algorithm for maximum Tukey depth.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Hervé Brönnimann

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Geometric Optimization Problems Over Sliding Windows.

[BibT_eX]

[DOI]

Bashir S. Sadjad

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Faster core-set constructions and data stream algorithms in fixed dimensions.

[BibT_eX]

[DOI]

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Towards in-place geometric algorithms and data structures.

[BibT_eX]

[DOI]

Hervé Brönnimann

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003

Polynomial-time approximation schemes for packing and piercing fat objects.

[BibT_eX]

[DOI]

J. Algorithms, 2003

Drawing K2, n: A lower bound.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

A Fully Dynamic Algorithm for Planar Width.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2003

On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

the asteroid surveying problem and other puzzles.

[BibT_eX]

[DOI]

Alexander Golynski

Claude-Guy Quimper

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

Euclidean bounded-degree spanning tree ratios.

[BibT_eX]

[DOI]

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

A Space-Efficient Algorithm for Segment Intersection.

[BibT_eX]

[DOI]

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

Curves of width one and the river shore problem.

[BibT_eX]

[DOI]

Alexander Golynski

Claude-Guy Quimper

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

2002

Optimizing area and aspect ration in straight-line orthogonal tree drawings.

[BibT_eX]

[DOI]

Comput. Geom., 2002

Dynamic subgraph connectivity with geometric applications.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Semi-online maintenance of geometric optima and measures.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Closest-point problems simplified on the RAM.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Low-Dimensional Linear Programming with Violations.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Drawing k2, n: A lower bound.

[BibT_eX]

[DOI]

Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles.

[BibT_eX]

[DOI]

Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

2001

Fly Cheaply: On the Minimum Fuel Consumption Problem.

[BibT_eX]

[DOI]

Alon Efrat

J. Algorithms, 2001

Dynamic planar convex hull operations in near-logarithmaic amortized time.

[BibT_eX]

[DOI]

J. ACM, 2001

A fully dynamic algorithm for planar.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Reporting curve segment intersections using restricted predicates.

[BibT_eX]

[DOI]

Comput. Geom., 2000

Balanced k-Colorings.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

On Levels in Arrangements of Curves.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999

More planar two-center algorithms.

[BibT_eX]

[DOI]

Comput. Geom., 1999

A Near-Linear Area Bound for Drawing Binary Trees.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Backwards Analysis of the Karger-Klein-Tarjan Algorithm for Minimum Spanning Trees.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1998

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1998

Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

On Enumerating and Selecting Distances.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

Geometric Applications of a Randomized Optimization Technique.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Jack Snoeyink

Chee-Keng Yap

Discret. Comput. Geom., 1997

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

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Approximate Nearest Neighbor Queries Revisited.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1996

Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1996

Fixed-Dimensional Linear Programming Queries Made Easy.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Jack Snoeyink

Chee-Keng Yap

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

The complexity of a single face of a minkowski sum.

[BibT_eX]

[DOI]

Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

1994

A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections.

[BibT_eX]