Wolfgang Mulzer

Discret. Comput. Geom., October, 2023

Flipping Plane Spanning Paths.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation, 2023

2022

Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

No-Dimensional Tverberg Theorems and Algorithms.

[BibT_eX]

[DOI]

Aruni Choudhary

Discret. Comput. Geom., 2022

Unique Sink Orientations of Grids is in Unique End of Potential Line.

[BibT_eX]

[DOI]

Michaela Borzechowski

CoRR, 2022

Flipping Plane Spanning Paths.

[BibT_eX]

[DOI]

CoRR, 2022

Nearest-Neighbor Decompositions of Drawings.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Well-Separation and Hyperplane Transversals in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Compatible Spanning Trees in Simple Drawings of Kn.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 30th International Symposium, 2022

Dynamic Connectivity in Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Long Plane Trees.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

On the Stretch Factor of Polygonal Chains.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Stabbing pairwise intersecting disks by five points.

[BibT_eX]

[DOI]

Discret. Math., 2021

Minimum cuts in geometric intersection graphs.

[BibT_eX]

[DOI]

Sergio Cabello

Comput. Geom., 2021

2020

A simple randomized $O(n \log n)$-time closest-pair algorithm in doubling metrics.

[BibT_eX]

[DOI]

Michiel Smid

Anil Maheshwari

J. Comput. Geom., 2020

Time-space trade-offs for computing Euclidean minimum spanning trees.

[BibT_eX]

[DOI]

Bahareh Banyassady

Luis Barba

J. Comput. Geom., 2020

Minimal Representations of Order Types by Geometric Graphs.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2020

A constructive proof of a concentration bound for real-valued random variables.

[BibT_eX]

[DOI]

Natalia Shenkman

Inf. Process. Lett., 2020

Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

Routing in Unit Disk Graphs without Dynamic Headers.

[BibT_eX]

[DOI]

Max Willert

CoRR, 2020

The Tree Stabbing Number is not Monotone.

[BibT_eX]

[DOI]

Johannes Obenaus

CoRR, 2020

Combinatorics of beacon-based routing in three dimensions.

[BibT_eX]

[DOI]

Jonas Cleve

Comput. Geom., 2020

Routing in polygonal domains.

[BibT_eX]

[DOI]

Comput. Geom., 2020

Reachability Oracles for Directed Transmission Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2020

Routing in Histograms.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation - 14th International Conference, 2020

Compact Routing in Unit Disk Graphs.

[BibT_eX]

[DOI]

Max Willert

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Computational Complexity of the α-Ham-Sandwich Problem.

[BibT_eX]

[DOI]

Man-Kwun Chiu

Aruni Choudhary

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Long Alternating Paths Exist.

[BibT_eX]

[DOI]

Pavel Valtr

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

2019

A time-space trade-off for computing the k-visibility region of a point in a polygon.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Dynamic Maintenance of the Lower Envelope of Pseudo-Lines.

[BibT_eX]

[DOI]

CoRR, 2019

Special Issue on the 34th European Workshop on Computational Geometry, Guest Editors' Foreword.

[BibT_eX]

[DOI]

Matias Korman

Comput. Geom., 2019

Faster algorithms for growing prioritized disks and rectangles.

[BibT_eX]

[DOI]

Comput. Geom., 2019

Asymmetric Convex Intersection Testing.

[BibT_eX]

[DOI]

Luis Barba

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model.

[BibT_eX]

[DOI]

Jonas Cleve

Proceedings of the Analysis of Experimental Algorithms - Special Event, 2019

Triangles and Girth in Disk Graphs and Transmission Graphs.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Computational Geometry Column 67.

[BibT_eX]

[DOI]

Bahareh Banyassady

Matias Korman

SIGACT News, 2018

Spanners for Directed Transmission Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Improved time-space trade-offs for computing Voronoi diagrams.

[BibT_eX]

[DOI]

J. Comput. Geom., 2018

Five Proofs of Chernoff's Bound with Applications.

[BibT_eX]

[DOI]

Bull. EATCS, 2018

Computational Aspects of the Colorful Carathéodory Theorem.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2018

Geometric Algorithms with Limited Workspace: A Survey.

[BibT_eX]

[DOI]

Bahareh Banyassady

Matias Korman

CoRR, 2018

Time-space trade-offs for triangulations and Voronoi diagrams.

[BibT_eX]

[DOI]

Comput. Geom., 2018

The dual diameter of triangulations.

[BibT_eX]

[DOI]

Comput. Geom., 2018

Routing in Unit Disk Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2018

Recognizing Generalized Transmission Graphs of Line Segments and Circular Sectors.

[BibT_eX]

[DOI]

Katharina Klost

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Approximate Minimum-Weight Matching with Outliers Under Translation.

[BibT_eX]

[DOI]

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

2017

An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2017

Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2017

Encoding Arguments.

[BibT_eX]

[DOI]

Pat Morin

Tommy Reddad

ACM Comput. Surv., 2017

Routing in Polygons with Holes.

[BibT_eX]

[DOI]

CoRR, 2017

Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation, 2017

Delta-Fast Tries: Local Searches in Bounded Universes with Linear Space.

[BibT_eX]

[DOI]

Marcel Ehrhardt

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

The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications.

[BibT_eX]

[DOI]

Frédéric Meunier

Pauline Sarrabezolles

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

2016

Approximability of the discrete Fréchet distance.

[BibT_eX]

[DOI]

Karl Bringmann

J. Comput. Geom., 2016

Computing the Fréchet Distance with a Retractable Leash.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2016

Time-Space Trade-off for Finding the k-Visibility Region of a Point in a Polygon.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Flip Distance Between Triangulations of a Simple Polygon is NP-Complete.

[BibT_eX]

[DOI]

Oswin Aichholzer

Alexander Pilz

Discret. Comput. Geom., 2015

Data Structures on Event Graphs.

[BibT_eX]

[DOI]

Bernard Chazelle

Algorithmica, 2015

Approximate k-flat Nearest Neighbor Search.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Spanners and Reachability Oracles for Directed Transmission Graphs.

[BibT_eX]

[DOI]

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

2014

Self-Improving Algorithms for Coordinatewise Maxima and Convex Hulls.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition.

[BibT_eX]

[DOI]

J. Comput. Geom., 2014

Algorithms for Tolerant Tverberg Partitions.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2014

Reprint of: Memory-constrained algorithms for simple polygons.

[BibT_eX]

[DOI]

Comput. Geom., 2014

Four Soviets Walk the Dog - with an Application to Alt's Conjecture.

[BibT_eX]

[DOI]

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

LiveCG: an Interactive Visualization Environment for Computational Geometry.

[BibT_eX]

[DOI]

Sebastian Kürten

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

Interference Minimization in Asymmetric Sensor Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2014

2013

Approximating Tverberg Points in Linear Time for Any Fixed Dimension.

[BibT_eX]

[DOI]

Daniel Werner

Discret. Comput. Geom., 2013

Unions of Onions

[BibT_eX]

[DOI]

CoRR, 2013

Convex hull of points lying on lines in time after preprocessing.

[BibT_eX]

[DOI]

Esther Ezra

Comput. Geom., 2013

Memory-constrained algorithms for simple polygons.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Unions of Onions: Preprocessing Imprecise Points for Fast Onion Layer Decomposition.

[BibT_eX]

[DOI]

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

Algorithms for Tolerated Tverberg Partitions.

[BibT_eX]

[DOI]

Jonathan Richard Shewchuk

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

Vertex Deletion for 3D Delaunay Triangulations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

2012

Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

A Static Optimality Transformation with Applications to Planar Point Location.

[BibT_eX]

[DOI]

John Iacono

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

Self-improving Algorithms for Coordinate-Wise Maxima and Convex Hulls

[BibT_eX]

[DOI]

CoRR, 2012

A Lower Bound for Shallow Partitions

[BibT_eX]

[DOI]

Daniel Werner

CoRR, 2012

Self-improving algorithms for coordinate-wise maxima.

[BibT_eX]

[DOI]

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

2011

Self-Improving Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Constant-Work-Space Algorithms for Geometric Problems.

[BibT_eX]

[DOI]

J. Comput. Geom., 2011

Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons.

[BibT_eX]

[DOI]

Tetsuo Asano

Yajun Wang

J. Graph Algorithms Appl., 2011

Delaunay triangulations in O(sort(n)) time and more.

[BibT_eX]

[DOI]

Kevin Buchin

J. ACM, 2011

Computing Hereditary Convex Structures.

[BibT_eX]

[DOI]

Bernard Chazelle

Discret. Comput. Geom., 2011

Convex Hull of Imprecise Points in o(n \log{n}) Time after Preprocessing

[BibT_eX]

[DOI]

Esther Ezra

CoRR, 2011

Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended.

[BibT_eX]

[DOI]

Algorithmica, 2011

Convex hull of imprecise points in o(n log n) time after preprocessing.

[BibT_eX]

[DOI]

Esther Ezra

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

2010

Constant-Work-Space Algorithm for a Shortest Path in a Simple Polygon.

[BibT_eX]

[DOI]

Tetsuo Asano

Yajun Wang

Proceedings of the WALCOM: Algorithms and Computation, 4th International Workshop, 2010

Self-improving Algorithms for Convex Hulls.

[BibT_eX]

[DOI]

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

2009

A note on predecessor searching in the pointer machine model.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Markov Incremental Constructions.

[BibT_eX]

[DOI]

Bernard Chazelle

Discret. Comput. Geom., 2009

Delaunay Triangulation of Imprecise Points Simplified and Extended.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Delaunay Triangulations in O(sort(n)) Time and More.

[BibT_eX]

[DOI]

Kevin Buchin

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

2008

Minimum-weight triangulation is NP-hard.

[BibT_eX]

[DOI]

Günter Rote

J. ACM, 2008

2005

An exclusion region for minimum dilation triangulations.

[BibT_eX]

[DOI]

Christian Knauer