John Hershberger

According to our database1, John Hershberger authored at least 115 papers between 1985 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2012, "For contributions to geometric computing and to design tools for integrated circuits.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Two Approaches to Building Time-Windowed Geometric Data Structures.
Algorithmica, 2019

2017
Hyperplane separability and convexity of probabilistic point sets.
JoCG, 2017

Shortest Paths in the Plane with Obstacle Violations.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
Geometric Shortest Paths in the Plane.
Encyclopedia of Algorithms, 2016

Bundled Crossings in Embedded Graphs.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

2015
Geometric k Shortest Paths.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Efficient Computation of Visibility Polygons.
CoRR, 2014

On the Complexity of Time-Dependent Shortest Paths.
Algorithmica, 2014

Geometric kth Shortest Paths: the Applet.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
Computing Shortest Paths amid Convex Pseudodisks.
SIAM J. Comput., 2013

Stable snap rounding.
Comput. Geom., 2013

A near-optimal algorithm for shortest paths among curved obstacles in the plane.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

2011
Guest editors' foreword.
ACM Journal of Experimental Algorithmics, 2011

Guest Editor's Foreword.
Discrete & Computational Geometry, 2011

The Union of Probabilistic Boxes: Maintaining the Volume.
Proceedings of the Algorithms - ESA 2011, 2011

A Discrete and Dynamic Version of Klee's Measure Problem.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010
Road Network Reconstruction for Organizing Paths.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2008
Summarizing spatial data streams using ClusterHulls.
ACM Journal of Experimental Algorithmics, 2008

Improved Output-Sensitive Snap Rounding.
Discrete & Computational Geometry, 2008

Adaptive sampling for geometric problems over data streams.
Comput. Geom., 2008

Simplified Planar Coresets for Data Streams.
Proceedings of the Algorithm Theory, 2008

2007
On the difficulty of some shortest path problems.
ACM Trans. Algorithms, 2007

Finding the k shortest simple paths: A new algorithm and its implementation.
ACM Trans. Algorithms, 2007

Sparse data aggregation in sensor networks.
Proceedings of the 6th International Conference on Information Processing in Sensor Networks, 2007

Approximate isocontours and spatial summaries for sensor networks.
Proceedings of the 6th International Conference on Information Processing in Sensor Networks, 2007

2006
Adaptive Spatial Partitioning for Multidimensional Data Streams.
Algorithmica, 2006

Cluster Hull: A Technique for Summarizing Spatial Data Streams.
Proceedings of the 22nd International Conference on Data Engineering, 2006

Contour Approximation in Sensor Networks.
Proceedings of the Distributed Computing in Sensor Systems, 2006

2005
Binary Space Partitions of Orthogonal Subdivisions.
SIAM J. Comput., 2005

Geometric spanners for routing in mobile networks.
IEEE Journal on Selected Areas in Communications, 2005

Smooth kinetic maintenance of clusters.
Comput. Geom., 2005

Polygonal path simplification with angle constraints.
Comput. Geom., 2005

Space complexity of hierarchical heavy hitters in multi-dimensional data streams.
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.
Inf. Process. Lett., 2004

Kinetic collision detection between two simple polygons.
Comput. Geom., 2004

Fractionally cascaded information in a sensor network.
Proceedings of the Third International Symposium on Information Processing in Sensor Networks, 2004

2003
Discrete Mobile Centers.
Discrete & Computational Geometry, 2003

Binary space partitions for 3D subdivisions.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Finding the k Shortest Simple Paths: A New Algorithm and Its Implementation.
Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002
Deformable Free-Space Tilings for Kinetic Collision Detection.
I. J. Robotics Res., 2002

Algorithmic issues in modeling motion.
ACM Comput. Surv., 2002

Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?".
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.
Int. J. Comput. Geometry Appl., 2001

Kinetic Connectivity for Unit Disks.
Discrete & Computational Geometry, 2001

Maintaining the Extent of a Moving Point Set.
Discrete & Computational Geometry, 2001

Simplified kinetic connectivity for rectangles and hypercubes.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Polygonal path approximation with angle constraints.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Geometric spanner for routing in mobile networks.
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?.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Morphing Simple Polygons.
Discrete & Computational Geometry, 2000

Lower Bounds for Kinetic Planar Subdivisions.
Discrete & Computational Geometry, 2000

1999
An Optimal Algorithm for Euclidean Shortest Paths in the Plane.
SIAM J. Comput., 1999

Data Structures for Mobile Data.
J. Algorithms, 1999

Kinetic Connectivity of Rectangles.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Kinetic Data Structures: Animating Proofs Through Time.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998
Practical methods for approximating shortest paths on a convex polytope in R3.
Comput. Geom., 1998

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

Erased arrangements of lines and convex decompositions of polyhedra.
Comput. Geom., 1998

1997
Matrix Searching with the Shortest-Path Metric.
SIAM J. Comput., 1997

Finding a Shortest Diagonal of a Simple Polygon in Linear Time.
Comput. Geom., 1997

Efficient Breakout Routing in Printed Circuit Boards (Extended Abstract).
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.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Efficient Breakout Routing in Printed Circuit Boards.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Snap Rounding Line Segments Efficiently in Two and Three Dimensions.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996
Efficiently Planning Compliant Motion in the Plane.
SIAM J. Comput., 1996

Off-Line Maintenance of Planar Configurations.
J. Algorithms, 1996

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

Optimal parallel algorithms for triangulated simple polygons.
Int. J. Comput. Geometry Appl., 1995

Practical Methods for Approximating Shortest Paths on a Convex Polytope in R3.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Morphing Binary Trees.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

The Centroid of Points with Approximate Weights.
Proceedings of the Algorithms, 1995

1994
Data Structures for Two-Edge Connectivity in Planar Graphs.
Theor. Comput. Sci., 1994

Selecting Heavily Covered Points.
SIAM J. Comput., 1994

Computing Minimum Length Paths of a Given Homotopy Class.
Comput. Geom., 1994

Ray Shooting in Polygons Using Geodesic Triangulations.
Algorithmica, 1994

An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Morphing Simple Polygons.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

An Efficient Solution to the Zookeeper's Problem.
Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993
A Faster Algorithm for the Two-Center Decision Problem.
Inf. Process. Lett., 1993

Approximating Polygons and Subdivisions with Minimum Link Paths.
Int. J. Comput. Geometry Appl., 1993

Computing the Intersection-Depth of Polyhedra.
Algorithmica, 1993

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

Efficient Computation of Euclidean Shortest Paths in the Plane
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Compliant Motion in a Simple Polygon.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992
Color and Sound in Algorithmic Animation.
IEEE Computer, 1992

Minimizing the Sum of Diameters Efficiently.
Comput. Geom., 1992

Upper Envelope Onion Peeling.
Comput. Geom., 1992

Applications of a Semi-Dynamic Convex Hull Algorithm.
BIT, 1992

Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra.
Proceedings of the Algorithm Theory, 1992

Fully Dynamic 2-Edge-Connectivity in Planar Graphs.
Proceedings of the Algorithm Theory, 1992

1991
Finding Tailored Partitions.
J. Algorithms, 1991

A New Data Structure for Shortest Path Queries in a Simple Polygon.
Inf. Process. Lett., 1991

Compact interval trees: a data structure for convex hulls.
Int. J. Comput. Geometry Appl., 1991

Computing Minimum Length Paths of a Given Homotopy Class (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 1991

Color and Sound in Algorithm Animation.
Proceedings of the 1991 IEEE Workshop on Visual Languages, Kobe, Japan, October 8-11, 1991, 1991

Offline Maintenance of Planar Configurations.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990
Input-Sensitive Compliant Motion in the Plane.
Proceedings of the SWAT 90, 1990

Implicitly Searching Convolutions and Computing Depth of Collision.
Proceedings of the Algorithms, 1990

Slimming Down by Adding: Selecting Heavily Covered Points.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Optimal Shortest Path Queries in a Simple Polygon.
J. Comput. Syst. Sci., 1989

Finding the Upper Envelope of n Line Segments in O(n log n) Time.
Inf. Process. Lett., 1989

Implicitly Representing Arrangements of Lines or Segments.
Discrete & Computational Geometry, 1989

On Arrangement of Jordan Arcs with Three Intersection per Pair.
Discrete & Computational Geometry, 1989

An Optimal Visibility Graph Algorithm for Triangulated Simple Polygons.
Algorithmica, 1989

Sweeping Arrangements of Curves.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Compliant Motion in a Simple Polygon.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

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

On Arrangements of Jordan Arcs with Three Intersections per Pair.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

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

Finding the Visibility Graph of a Simple Polygon in Time Proportional to its Size.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986
Visibility of Disjoint Polygons.
Algorithmica, 1986

Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons.
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.
Bulletin of the EATCS, 1985

A polynomial time algorithm for finding the prime factors of cartesian-product graphs.
Discrete Applied Mathematics, 1985

Visibility-Polygon Search and Euclidean Shortest Paths
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985


  Loading...