John Hershberger

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

2019

Two Approaches to Building Time-Windowed Geometric Data Structures.

[BibT_eX]

[DOI]

Timothy M. Chan

Simon Pratt

Algorithmica, 2019

2017

Shortest Paths in the Plane with Obstacle Violations.

[BibT_eX]

[DOI]

Neeraj Kumar

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

2016

Geometric Shortest Paths in the Plane.

[BibT_eX]

[DOI]

Sylvester David Eriksson-Bique

Encyclopedia of Algorithms, 2016

Bundled Crossings in Embedded Graphs.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Hyperplane Separability and Convexity of Probabilistic Point Sets.

[BibT_eX]

[DOI]

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

2015

Geometric k Shortest Paths.

[BibT_eX]

[DOI]

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

2014

Efficient Computation of Visibility Polygons.

[BibT_eX]

[DOI]

CoRR, 2014

Geometric kth Shortest Paths: the Applet.

[BibT_eX]

[DOI]

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

2013

Computing Shortest Paths amid Convex Pseudodisks.

[BibT_eX]

[DOI]

Danny Z. Chen

Haitao Wang

SIAM J. Comput., 2013

A near-optimal algorithm for shortest paths among curved obstacles in the plane.

[BibT_eX]

[DOI]

Hakan Yildiz

Proceedings of the Symposium on Computational Geometry 2013, 2013

2011

Guest editors' foreword.

[BibT_eX]

[DOI]

Irene Finocchi

ACM J. Exp. Algorithmics, 2011

Guest Editor's Foreword.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2011

On the Complexity of Time-Dependent Shortest Paths.

[BibT_eX]

[DOI]

Luca Foschini

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

The Union of Probabilistic Boxes: Maintaining the Volume.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

Stable snap rounding.

[BibT_eX]

[DOI]

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

A Discrete and Dynamic Version of Klee's Measure Problem.

[BibT_eX]

[DOI]

Hakan Yildiz

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

2010

Road Network Reconstruction for Organizing Paths.

[BibT_eX]

[DOI]

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

2008

Simplified Planar Coresets for Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2008

2007

Finding the k shortest simple paths: A new algorithm and its implementation.

[BibT_eX]

[DOI]

Matthew Maxel

ACM Trans. Algorithms, 2007

Sparse data aggregation in sensor networks.

[BibT_eX]

[DOI]

Proceedings of the 6th International Conference on Information Processing in Sensor Networks, 2007

Approximate isocontours and spatial summaries for sensor networks.

[BibT_eX]

[DOI]

Sorabh Gandhi

Proceedings of the 6th International Conference on Information Processing in Sensor Networks, 2007

2006

Cluster Hull: A Technique for Summarizing Spatial Data Streams.

[BibT_eX]

[DOI]

Nisheeth Shrivastava

Proceedings of the 22nd International Conference on Data Engineering, 2006

Contour Approximation in Sensor Networks.

[BibT_eX]

[DOI]

Chiranjeeb Buragohain

Sorabh Gandhi

Proceedings of the Distributed Computing in Sensor Systems, 2006

Improved output-sensitive snap rounding.

[BibT_eX]

[DOI]

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Summarizing Spatial Data Streams Using ClusterHulls.

[BibT_eX]

[DOI]

Nisheeth Shrivastava

Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments, 2006

2005

Geometric spanners for routing in mobile networks.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2005

Polygonal path simplification with angle constraints.

[BibT_eX]

[DOI]

Comput. Geom., 2005

Space complexity of hierarchical heavy hitters in multi-dimensional data streams.

[BibT_eX]

[DOI]

Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

2004

Kinetic collision detection with fast flight plan changes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Adaptive Sampling for Geometric Problems over Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Adaptive Spatial Partitioning for Multidimensional Data Streams.

[BibT_eX]

[DOI]

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

Fractionally cascaded information in a sensor network.

[BibT_eX]

[DOI]

Proceedings of the Third International Symposium on Information Processing in Sensor Networks, 2004

Binary space partitions of orthogonal subdivisions.

[BibT_eX]

[DOI]

Csaba D. Tóth

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

2003

On the Difficulty of Some Shortest Path Problems.

[BibT_eX]

[DOI]

Amit M. Bhosle

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Binary space partitions for 3D subdivisions.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Smooth kinetic maintenance of clusters.

[BibT_eX]

[DOI]

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

Finding the k Shortest Simple Paths: A New Algorithm and Its Implementation.

[BibT_eX]

Matthew Maxel

Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002

Deformable Free-Space Tilings for Kinetic Collision Detection.

[BibT_eX]

[DOI]

Int. J. Robotics Res., 2002

Algorithmic issues in modeling motion.

[BibT_eX]

[DOI]

ACM Comput. Surv., 2002

Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?".

[BibT_eX]

[DOI]

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

2001

Guest Editor's Foreword - Selected Papers from the Fourteenth ACM Symposium on Computational Geometry, Minneapolis, Minnesota, June 1998.

[BibT_eX]

Int. J. Comput. Geom. Appl., 2001

Simplified kinetic connectivity for rectangles and hypercubes.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Polygonal path approximation with angle constraints.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Geometric spanner for routing in mobile networks.

[BibT_eX]

[DOI]

Proceedings of the 2nd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2001

Vickrey Prices and Shortest Paths: What is an Edge Worth?.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Discrete mobile centers.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000

Morphing Simple Polygons.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2000

Kinetic connectivity for unit disks.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999

An Optimal Algorithm for Euclidean Shortest Paths in the Plane.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Kinetic Collision Detection Between Two Simple Polygons.

[BibT_eX]

[DOI]

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

Kinetic Connectivity of Rectangles.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Kinetic Data Structures: Animating Proofs Through Time.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Lower Bounds for Kinetic Planar Subdivisions.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

Practical methods for approximating shortest paths on a convex polytope in R3.

[BibT_eX]

[DOI]

Comput. Geom., 1998

Cartographic line simplification and polygon CSG formulæ in O(nlog * n) time.

[BibT_eX]

[DOI]

Comput. Geom., 1998

Erased arrangements of lines and convex decompositions of polyhedra.

[BibT_eX]

[DOI]

Comput. Geom., 1998

1997

Finding a Shortest Diagonal of a Simple Polygon in Linear Time.

[BibT_eX]

[DOI]

Comput. Geom., 1997

Efficient Breakout Routing in Printed Circuit Boards (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Cartographic Line Simplification and Polygon CSG Formulae and in O(n log* n) Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Maintaining the Extent of a Moving Point Set.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Data Structures for Mobile Data.

[BibT_eX]

[DOI]

Julien Basch

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

Efficient Breakout Routing in Printed Circuit Boards.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Snap Rounding Line Segments Efficiently in Two and Three Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

Efficiently Planning Compliant Motion in the Plane.

[BibT_eX]

[DOI]

Joseph Friedman

SIAM J. Comput., 1996

Off-Line Maintenance of Planar Configurations.

[BibT_eX]

[DOI]

J. Algorithms, 1996

1995

Practical Methods for Approximating Shortest Paths on a Convex Polytope in R3.

[BibT_eX]

[DOI]

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

Morphing Binary Trees.

[BibT_eX]

[DOI]

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

The Centroid of Points with Approximate Weights.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1995

1994

Data Structures for Two-Edge Connectivity in Planar Graphs.

[BibT_eX]

[DOI]

Monika Rauch

Theor. Comput. Sci., 1994

Selecting Heavily Covered Points.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Computing Minimum Length Paths of a Given Homotopy Class.

[BibT_eX]

[DOI]

Comput. Geom., 1994

An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Morphing Simple Polygons.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

An Efficient Solution to the Zookeeper's Problem.

[BibT_eX]

Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993

A Faster Algorithm for the Two-Center Decision Problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1993

Computing the Intersection-Depth of Polyhedra.

[BibT_eX]

[DOI]

Algorithmica, 1993

Matrix searching with the shortest path metric.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Efficient Computation of Euclidean Shortest Paths in the Plane

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Compliant Motion in a Simple Polygon.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992

Color and Sound in Algorithmic Animation.

[BibT_eX]

[DOI]

Marc H. Brown

Computer, 1992

Minimizing the Sum of Diameters Efficiently.

[BibT_eX]

[DOI]

Comput. Geom., 1992

Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1992

Fully Dynamic 2-Edge-Connectivity in Planar Graphs.

[BibT_eX]

[DOI]

Monika Rauch

Proceedings of the Algorithm Theory, 1992

Optimal Parallel Algorithms for Triangulated Simple Polygons.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991

A New Data Structure for Shortest Path Queries in a Simple Polygon.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

Computing Minimum Length Paths of a Given Homotopy Class (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 1991

Color and Sound in Algorithm Animation.

[BibT_eX]

[DOI]

Marc H. Brown

Proceedings of the 1991 IEEE Workshop on Visual Languages, Kobe, Japan, October 8-11, 1991, 1991

Offline Maintenance of Planar Configurations.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Approximating Polygons and Subdivisions with Minimum Link Paths.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

Proceedings of the ISA '91 Algorithms, 1991

Ray Shooting in Polygons Using Geodesic Triangulations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

1990

Applications of a Semi-Dynamic Convex Hull Algorithm.

[BibT_eX]

[DOI]

Proceedings of the SWAT 90, 1990

Upper Envelope Onion Peeling.

[BibT_eX]

[DOI]

Proceedings of the SWAT 90, 1990

Input-Sensitive Compliant Motion in the Plane.

[BibT_eX]

[DOI]

Joseph Friedman

Proceedings of the SWAT 90, 1990

Compact Interval Trees: A Data Structure for Convex Hulls.

[BibT_eX]

[DOI]

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

Implicitly Searching Convolutions and Computing Depth of Collision.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1990

Slimming Down by Adding: Selecting Heavily Covered Points.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989

Finding the Upper Envelope of n Line Segments in O(n log n) Time.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1989

On Arrangement of Jordan Arcs with Three Intersection per Pair.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1989

An Optimal Visibility Graph Algorithm for Triangulated Simple Polygons.

[BibT_eX]

[DOI]

Algorithmica, 1989

Sweeping Arrangements of Curves.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Finding Tailored Partitions.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Compliant Motion in a Simple Polygon.

[BibT_eX]

[DOI]

Joseph Friedman

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988

An O(n²) Shortest Path Algorithm for a Non-Rotating Convex Body.

[BibT_eX]

[DOI]

J. Algorithms, 1988

An efficient algorithm for finding the CSG representation of a simple polygon.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, 1988

Implicitly Representing Arrangements of Lines or Segments.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On Arrangements of Jordan Arcs with Three Intersections per Pair.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987

Efficient algorithms for shortest path and visibility problems.

[BibT_eX]

[DOI]

PhD thesis, 1987

Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons.

[BibT_eX]

[DOI]

Algorithmica, 1987

Finding the Visibility Graph of a Simple Polygon in Time Proportional to its Size.

[BibT_eX]

[DOI]

Proceedings of the Third Annual Symposium on Computational Geometry, 1987

Optimal Shortest Path Queries in a Simple Polygon.

[BibT_eX]

[DOI]

Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986

Visibility of Disjoint Polygons.

[BibT_eX]

[DOI]

Algorithmica, 1986

Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985

Computing the visibility graphs of n line segments in O(nn) time.

[BibT_eX]

Bull. EATCS, 1985

A polynomial time algorithm for finding the prime factors of cartesian-product graphs.

[BibT_eX]

[DOI]

Joan Feigenbaum