John Hershberger

According to our database, John Hershberger authored at least 116 papers between 1985 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2022

A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane.

John Hershberger, Subhash Suri, Hakan Yildiz

SIAM J. Comput., June, 2022

2020

Shortest Paths in the Plane with Obstacle Violations.

John Hershberger, Neeraj Kumar, Subhash Suri

Algorithmica, 2020

2019

Two Approaches to Building Time-Windowed Geometric Data Structures.

Timothy M. Chan, John Hershberger, Simon Pratt

Algorithmica, 2019

2017

Hyperplane separability and convexity of probabilistic point sets.

Martin Fink, John Hershberger, Nirman Kumar, Subhash Suri

J. Comput. Geom., 2017

2016

Geometric Shortest Paths in the Plane.

John Hershberger

Encyclopedia of Algorithms, 2016

Bundled Crossings in Embedded Graphs.

Martin Fink, John Hershberger, Subhash Suri, Kevin Verbeek

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

2015

Geometric <i>k</i> Shortest Paths.

Sylvester David Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeek, Hakan Yildiz

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

2014

Efficient Computation of Visibility Polygons.

Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang, Alexander Kröller

CoRR, 2014

On the Complexity of Time-Dependent Shortest Paths.

Luca Foschini, John Hershberger, Subhash Suri

Algorithmica, 2014

Geometric kth Shortest Paths: the Applet.

John Hershberger, Valentin Polishchuk, Bettina Speckmann, Topi Talvitie

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

2013

Computing Shortest Paths amid Convex Pseudodisks.

Danny Z. Chen, John Hershberger, Haitao Wang

SIAM J. Comput., 2013

Stable snap rounding.

John Hershberger

Comput. Geom., 2013

2011

Guest editors' foreword.

Irene Finocchi, John Hershberger

ACM J. Exp. Algorithmics, 2011

Guest Editor's Foreword.

John Hershberger

Discret. Comput. Geom., 2011

The Union of Probabilistic Boxes: Maintaining the Volume.

Hakan Yildiz, Luca Foschini, John Hershberger, Subhash Suri

Proceedings of the Algorithms - ESA 2011, 2011

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

Hakan Yildiz, John Hershberger, Subhash Suri

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

2010

Road Network Reconstruction for Organizing Paths.

Daniel Chen, Leonidas J. Guibas, John Hershberger, Jian Sun

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

2008

Summarizing spatial data streams using ClusterHulls.

John Hershberger, Nisheeth Shrivastava, Subhash Suri

ACM J. Exp. Algorithmics, 2008

Improved Output-Sensitive Snap Rounding.

John Hershberger

Discret. Comput. Geom., 2008

Adaptive sampling for geometric problems over data streams.

John Hershberger, Subhash Suri

Comput. Geom., 2008

Simplified Planar Coresets for Data Streams.

John Hershberger, Subhash Suri

Proceedings of the Algorithm Theory, 2008

2007

On the difficulty of some shortest path problems.

John Hershberger, Subhash Suri, Amit M. Bhosle

ACM Trans. Algorithms, 2007

Finding the <i>k</i> shortest simple paths: A new algorithm and its implementation.

John Hershberger, Matthew Maxel, Subhash Suri

ACM Trans. Algorithms, 2007

Sparse data aggregation in sensor networks.

Jie Gao, Leonidas J. Guibas, Nikola Milosavljevic, John Hershberger

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

Approximate isocontours and spatial summaries for sensor networks.

Sorabh Gandhi, John Hershberger, Subhash Suri

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

2006

Adaptive Spatial Partitioning for Multidimensional Data Streams.

John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth

Algorithmica, 2006

Cluster Hull: A Technique for Summarizing Spatial Data Streams.

John Hershberger, Nisheeth Shrivastava, Subhash Suri

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

Contour Approximation in Sensor Networks.

Chiranjeeb Buragohain, Sorabh Gandhi, John Hershberger, Subhash Suri

Proceedings of the Distributed Computing in Sensor Systems, 2006

2005

Binary Space Partitions of Orthogonal Subdivisions.

John Hershberger, Subhash Suri, Csaba D. Tóth

SIAM J. Comput., 2005

Geometric spanners for routing in mobile networks.

Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu

IEEE J. Sel. Areas Commun., 2005

Smooth kinetic maintenance of clusters.

John Hershberger

Comput. Geom., 2005

Polygonal path simplification with angle constraints.

Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Ningfang Mi, Jack Snoeyink

Comput. Geom., 2005

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

John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth

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.

John Hershberger

Inf. Process. Lett., 2004

Kinetic collision detection between two simple polygons.

Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang

Comput. Geom., 2004

Fractionally cascaded information in a sensor network.

Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang

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

2003

Discrete Mobile Centers.

Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu

Discret. Comput. Geom., 2003

Binary space partitions for 3D subdivisions.

John Hershberger, Subhash Suri

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

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

John Hershberger, Matthew Maxel, Subhash Suri

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

2002

Deformable Free-Space Tilings for Kinetic Collision Detection.

Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang

Int. J. Robotics Res., 2002

Algorithmic issues in modeling motion.

Pankaj K. Agarwal, Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, Sariel Har-Peled, John Hershberger, Christian S. Jensen, Lydia E. Kavraki, Patrice Koehl, Ming C. Lin, Dinesh Manocha, Dimitris N. Metaxas, Brian Mirtich, David M. Mount, S. Muthukrishnan, Dinesh K. Pai, Elisha Sacks, Jack Snoeyink, Subhash Suri, Ouri Wolfson

ACM Comput. Surv., 2002

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

John Hershberger, Subhash Suri

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

2001

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

John Hershberger

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

Kinetic Connectivity for Unit Disks.

Leonidas J. Guibas, John Hershberger, Subhash Suri, Li Zhang

Discret. Comput. Geom., 2001

Maintaining the Extent of a Moving Point Set.

Pankaj K. Agarwal, Leonidas J. Guibas, John Hershberger, Eric Veach

Discret. Comput. Geom., 2001

Simplified kinetic connectivity for rectangles and hypercubes.

John Hershberger, Subhash Suri

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Polygonal path approximation with angle constraints.

Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Jack Snoeyink

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Geometric spanner for routing in mobile networks.

Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu

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?.

John Hershberger, Subhash Suri

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

2000

Morphing Simple Polygons.

Leonidas J. Guibas, John Hershberger, Subhash Suri

Discret. Comput. Geom., 2000

Lower Bounds for Kinetic Planar Subdivisions.

Pankaj K. Agarwal, Julien Basch, Mark de Berg, Leonidas J. Guibas, John Hershberger

Discret. Comput. Geom., 2000

1999

An Optimal Algorithm for Euclidean Shortest Paths in the Plane.

John Hershberger, Subhash Suri

SIAM J. Comput., 1999

Data Structures for Mobile Data.

Julien Basch, Leonidas J. Guibas, John Hershberger

J. Algorithms, 1999

Kinetic Connectivity of Rectangles.

John Hershberger, Subhash Suri

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Kinetic Data Structures: Animating Proofs Through Time.

Julien Basch, João Comba, Leonidas J. Guibas, John Hershberger, Craig Silverstein, Li Zhang

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

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

John Hershberger, Subhash Suri

Comput. Geom., 1998

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

John Hershberger, Jack Snoeyink

Comput. Geom., 1998

Erased arrangements of lines and convex decompositions of polyhedra.

John Hershberger, Jack Snoeyink

Comput. Geom., 1998

1997

Matrix Searching with the Shortest-Path Metric.

John Hershberger, Subhash Suri

SIAM J. Comput., 1997

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

John Hershberger, Subhash Suri

Comput. Geom., 1997

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

John Hershberger, Subhash Suri

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.

John Hershberger, Jack Snoeyink

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

Efficient Breakout Routing in Printed Circuit Boards.

John Hershberger, Subhash Suri

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Snap Rounding Line Segments Efficiently in Two and Three Dimensions.

Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tanenbaum

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

Efficiently Planning Compliant Motion in the Plane.

Joseph Friedman, John Hershberger, Jack Snoeyink

SIAM J. Comput., 1996

Off-Line Maintenance of Planar Configurations.

John Hershberger, Subhash Suri

J. Algorithms, 1996

1995

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

John Hershberger, Subhash Suri

J. Algorithms, 1995

Optimal parallel algorithms for triangulated simple polygons.

John Hershberger

Int. J. Comput. Geom. Appl., 1995

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

John Hershberger, Subhash Suri

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

Morphing Binary Trees.

John Hershberger, Subhash Suri

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

The Centroid of Points with Approximate Weights.

Marshall W. Bern, David Eppstein, Leonidas J. Guibas, John Hershberger, Subhash Suri, Jan Wolter

Proceedings of the Algorithms, 1995

1994

Data Structures for Two-Edge Connectivity in Planar Graphs.

John Hershberger, Monika Rauch, Subhash Suri

Theor. Comput. Sci., 1994

Selecting Heavily Covered Points.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir

SIAM J. Comput., 1994

Computing Minimum Length Paths of a Given Homotopy Class.

John Hershberger, Jack Snoeyink

Comput. Geom., 1994

Ray Shooting in Polygons Using Geodesic Triangulations.

Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, John Hershberger, Micha Sharir, Jack Snoeyink

Algorithmica, 1994

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

John Hershberger, Jack Snoeyink

Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Morphing Simple Polygons.

Leonidas J. Guibas, John Hershberger

Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

An Efficient Solution to the Zookeeper's Problem.

John Hershberger, Jack Snoeyink

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

1993

A Faster Algorithm for the Two-Center Decision Problem.

John Hershberger

Inf. Process. Lett., 1993

Approximating Polygons and Subdivisions with Minimum Link Paths.

Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, Jack Snoeyink

Int. J. Comput. Geom. Appl., 1993

Computing the Intersection-Depth of Polyhedra.

David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri

Algorithmica, 1993

An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon.

David P. Dobkin, Leonidas J. Guibas, John Hershberger, Jack Snoeyink

Algorithmica, 1993

Efficient Computation of Euclidean Shortest Paths in the Plane

John Hershberger, Subhash Suri

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

Compliant Motion in a Simple Polygon.

John Hershberger

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

1992

Color and Sound in Algorithmic Animation.

Marc H. Brown, John Hershberger

Computer, 1992

Minimizing the Sum of Diameters Efficiently.

John Hershberger

Comput. Geom., 1992

Upper Envelope Onion Peeling.

John Hershberger

Comput. Geom., 1992

Applications of a Semi-Dynamic Convex Hull Algorithm.

John Hershberger, Subhash Suri

BIT, 1992

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

John Hershberger, Jack Snoeyink

Proceedings of the Algorithm Theory, 1992

Fully Dynamic 2-Edge-Connectivity in Planar Graphs.

John Hershberger, Monika Rauch, Subhash Suri

Proceedings of the Algorithm Theory, 1992

1991

Finding Tailored Partitions.

John Hershberger, Subhash Suri

J. Algorithms, 1991

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

John Hershberger

Inf. Process. Lett., 1991

Compact interval trees: a data structure for convex hulls.

Leonidas J. Guibas, John Hershberger, Jack Snoeyink

Int. J. Comput. Geom. Appl., 1991

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

John Hershberger, Jack Snoeyink

Proceedings of the Algorithms and Data Structures, 1991

Color and Sound in Algorithm Animation.

Marc H. Brown, John Hershberger

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

Offline Maintenance of Planar Configurations.

John Hershberger, Subhash Suri

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

1990

Input-Sensitive Compliant Motion in the Plane.

Joseph Friedman, John Hershberger, Jack Snoeyink

Proceedings of the SWAT 90, 1990

Implicitly Searching Convolutions and Computing Depth of Collision.

David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri

Proceedings of the Algorithms, 1990

Slimming Down by Adding: Selecting Heavily Covered Points.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir

Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989

Optimal Shortest Path Queries in a Simple Polygon.

Leonidas J. Guibas, John Hershberger

J. Comput. Syst. Sci., 1989

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

John Hershberger

Inf. Process. Lett., 1989

Implicitly Representing Arrangements of Lines or Segments.

Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, Emo Welzl

Discret. Comput. Geom., 1989

On Arrangement of Jordan Arcs with Three Intersection per Pair.

Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink

Discret. Comput. Geom., 1989

An Optimal Visibility Graph Algorithm for Triangulated Simple Polygons.

John Hershberger

Algorithmica, 1989

Sweeping Arrangements of Curves.

Jack Snoeyink, John Hershberger

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Compliant Motion in a Simple Polygon.

Joseph Friedman, John Hershberger, Jack Snoeyink

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988

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

John Hershberger, Leonidas J. Guibas

J. Algorithms, 1988

On Arrangements of Jordan Arcs with Three Intersections per Pair.

Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987

Efficient algorithms for shortest path and visibility problems.

John Hershberger

PhD thesis, 1987

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

Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan

Algorithmica, 1987

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

John Hershberger

Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986

Visibility of Disjoint Polygons.

Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai

Algorithmica, 1986

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

Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan

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

1985

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

Leonidas J. Guibas, John Hershberger

Bull. EATCS, 1985

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

Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer

Discret. Appl. Math., 1985

Visibility-Polygon Search and Euclidean Shortest Paths

Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985