Timothy M. Chan

Comput. Geom., 2022

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

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Yinzhan Xu

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]

Da Wei Zheng

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

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

[BibT_eX]

[DOI]

R. Ryan Williams

ACM Trans. Algorithms, 2021

More dynamic data structures for geometric set cover with sublinear update time.

[BibT_eX]

[DOI]

J. Comput. Geom., 2021

Smallest k-Enclosing Rectangle Revisited.

[BibT_eX]

[DOI]

Sariel Har-Peled

Discret. Comput. Geom., 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]

Virginia Vassilevska Williams

Yinzhan Xu

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

Dynamic Colored Orthogonal Range Searching.

[BibT_eX]

[DOI]

Zhengcheng Huang

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

2020

More Logarithmic-factor Speedups for 3SUM, (median, +)-convolution, and Some Geometric 3SUM-hard Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

On Locality-Sensitive Orderings and Their Applications.

[BibT_eX]

[DOI]

Sariel Har-Peled

Mitchell Jones

SIAM J. Comput., 2020

Dynamic Geometric Data Structures via Shallow Cuttings.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

Tree Drawings Revisited.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

Range closest-pair search in higher dimensions.

[BibT_eX]

[DOI]

Saladi Rahul

Jie Xue

Comput. Geom., 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]

Zhengcheng Huang

Proceedings of the Graph Drawing and Network Visualization - 28th International Symposium, 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

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

[BibT_eX]

[DOI]

J. Comput. Geom., 2019

All-Pairs Shortest Paths in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

J. Comput. Geom., 2019

Subquadratic encodings for point configurations.

[BibT_eX]

[DOI]

J. Comput. Geom., 2019

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

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2019

Faster Approximate Diameter and Distance Oracles in Planar Graphs.

[BibT_eX]

[DOI]

Algorithmica, 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

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

2018

Selection and Sorting in the "Restore" Model.

[BibT_eX]

[DOI]

J. Ian Munro

Venkatesh Raman

ACM Trans. Algorithms, 2018

Improved Deterministic Algorithms for Linear Programming in Low Dimensions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Towards an Optimal Method for Dynamic Planar Point Location.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Dynamic Orthogonal Range Searching on the RAM, Revisited.

[BibT_eX]

[DOI]

J. Comput. Geom., 2018

Applications of Chebyshev polynomials to low-dimensional computational geometry.

[BibT_eX]

[DOI]

J. Comput. Geom., 2018

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

[BibT_eX]

[DOI]

Inf. Process. Lett., 2018

A Clustering-Based Approach to Kinetic Closest Pair.

[BibT_eX]

[DOI]

Algorithmica, 2018

Approximation Schemes for 0-1 Knapsack.

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Simplicity in 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

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time.

[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

Instance-Optimal Geometric Algorithms.

[BibT_eX]

[DOI]

Jérémy Barbay

J. ACM, 2017

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

[BibT_eX]

[DOI]

Comput. Geom., 2017

Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points.

[BibT_eX]

[DOI]

Comput. Geom., 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

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

2016

Adaptive and Approximate Orthogonal Range Counting.

[BibT_eX]

[DOI]

Bryan T. Wilkinson

ACM Trans. Algorithms, 2016

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

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2016

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

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

Drawing Partially Embedded and Simultaneously Planar Graphs.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2015

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

[BibT_eX]

[DOI]

Patrick Lee

Discret. Comput. Geom., 2015

Guest Editor's foreword.

[BibT_eX]

[DOI]

Rolf Klein

Comput. Geom., 2015

Geometric red-blue set cover for unit squares and related problems.

[BibT_eX]

[DOI]

Nan Hu

Comput. Geom., 2015

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

[BibT_eX]

[DOI]

Algorithmica, 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

Fast String Dictionary Lookup with One Error.

[BibT_eX]

[DOI]

Moshe Lewenstein

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

Time-Windowed Closest Pair.

[BibT_eX]

[DOI]

Simon Pratt

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

2014

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

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Maximum-weight planar boxes in O(n2) time (and better).

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Guest Editors' Foreword.

[BibT_eX]

[DOI]

Rolf Klein

Discret. Comput. Geom., 2014

Closest pair and the post office problem for stochastic points.

[BibT_eX]

[DOI]

Pegah Kamousi

Subhash Suri

Comput. Geom., 2014

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions.

[BibT_eX]

[DOI]

Vinayak Pathak

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

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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 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

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 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

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

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

Three Problems about Dynamic Convex Hulls.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2012

Approximation Algorithms for Maximum Independent Set of Pseudo-Disks.

[BibT_eX]

[DOI]

Sariel Har-Peled

Discret. Comput. Geom., 2012

On Levels in Arrangements of Surfaces in Three Dimensions.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2012

Optimal Partition Trees.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

Dynamic Connectivity: Connecting to Networks and Geometry.

[BibT_eX]

[DOI]

Liam Roditty

SIAM J. Comput., 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

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

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

On the bichromatic k-set problem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Comparison-based time-space lower bounds for selection.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

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

[BibT_eX]

[DOI]

J. ACM, 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

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

[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

2009

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

A Randomized Algorithm for Online Unit Clustering.

[BibT_eX]

[DOI]

Hamid Zarrabi-Zadeh

Theory Comput. Syst., 2009

Dynamic Coresets.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2009

On Approximate Range Counting and Depth.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2009

Dynamic ham-sandwich cuts in the plane.

[BibT_eX]

[DOI]

Comput. Geom., 2009

An Improved Algorithm for Online Unit Clustering.

[BibT_eX]

[DOI]

Hamid Zarrabi-Zadeh

Algorithmica, 2009

Dynamic Connectivity for Axis-Parallel Rectangles.

[BibT_eX]

[DOI]

Algorithmica, 2009

Optimal halfspace range reporting in three dimensions.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

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

[BibT_eX]

[DOI]

Algorithmica, 2008

In-place 2-d nearest neighbor search.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

2007

Multi-Pass Geometric Algorithms.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

2006

Dynamic Subgraph Connectivity with Geometric Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Geometric Optimization Problems over Sliding Windows.

[BibT_eX]

[DOI]

Bashir S. Sadjad

Int. J. Comput. Geom. Appl., 2006

Three problems about simple polygons.

[BibT_eX]

[DOI]

Comput. Geom., 2006

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

[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

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 (FOCS 2006), 2006

Necklaces, Convolutions, and X + Y.

[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

Low-Dimensional Linear Programming with Violations.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

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

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

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

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

Euclidean Bounded-Degree Spanning Tree Ratios.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

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

Semi-Online Maintenance of Geometric Optima and Measures.

[BibT_eX]

[DOI]

SIAM J. Comput., 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.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

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

Approximating the Diameter, Width, Smallest Enclosing Cylinder, and Minimum-Width Annulus.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2002

Balanced k-colorings.

[BibT_eX]

[DOI]

Discret. Math., 2002

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

[BibT_eX]

[DOI]

Comput. Geom., 2002

A Near-Linear Area Bound for Drawing Binary Trees.

[BibT_eX]

[DOI]

Algorithmica, 2002

Closest-point problems simplified on the RAM.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

On Enumerating and Selecting Distances.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 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

1999

Geometric Applications of a Randomized Optimization Technique.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1999

More planar two-center algorithms.

[BibT_eX]

[DOI]

Comput. Geom., 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

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

[BibT_eX]

[DOI]

J. Algorithms, 1998

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

[BibT_eX]

[DOI]

Inf. Process. Lett., 1998

Approximate Nearest Neighbor Queries Revisited.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

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

1996

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

[BibT_eX]

[DOI]

Discret. Comput. Geom., 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

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]