John Hershberger

150 papers A* 27A 7B 8Journal 66Unranked 39

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	Snap Rounding: A Cautionary Tale. SoCG John Hershberger
2022	J	`jnl`	A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane. SIAM J. Comput. John Hershberger, Subhash Suri, Hakan Yildiz
2020	J	`jnl`	Shortest Paths in the Plane with Obstacle Violations. Algorithmica John Hershberger, Neeraj Kumar, Subhash Suri
2019	J	`jnl`	Two Approaches to Building Time-Windowed Geometric Data Structures. Algorithmica Timothy M. Chan, John Hershberger, Simon Pratt
2017	J	`jnl`	Hyperplane separability and convexity of probabilistic point sets. J. Comput. Geom. Martin Fink, John Hershberger, Nirman Kumar, Subhash Suri
2017	A	`conf`	Shortest Paths in the Plane with Obstacle Violations. ESA John Hershberger, Neeraj Kumar, Subhash Suri
2016	B	`conf`	Bundled Crossings in Embedded Graphs. LATIN Martin Fink, John Hershberger, Subhash Suri, Kevin Verbeek
2016	—	`ch.`	Geometric Shortest Paths in the Plane. Encyclopedia of Algorithms John Hershberger
2016	A*	`conf`	Hyperplane Separability and Convexity of Probabilistic Point Sets. SoCG Martin Fink, John Hershberger, Nirman Kumar, Subhash Suri
2015	A*	`conf`	Geometric SODA Sylvester David Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeek, Hakan Yildiz
2014	J	`jnl`	Efficient Computation of Visibility Polygons. CoRR Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang, Alexander Kröller
2014	A*	`conf`	Geometric kth Shortest Paths: the Applet. SoCG John Hershberger, Valentin Polishchuk, Bettina Speckmann, Topi Talvitie
2014	J	`jnl`	On the Complexity of Time-Dependent Shortest Paths. Algorithmica Luca Foschini, John Hershberger, Subhash Suri
2013	A*	`conf`	A near-optimal algorithm for shortest paths among curved obstacles in the plane. SoCG John Hershberger, Subhash Suri, Hakan Yildiz
2013	J	`jnl`	Computing Shortest Paths amid Convex Pseudodisks. SIAM J. Comput. Danny Z. Chen, John Hershberger, Haitao Wang
2013	J	`jnl`	Stable snap rounding. Comput. Geom. John Hershberger
2011	—	`conf`	A Discrete and Dynamic Version of Klee's Measure Problem. CCCG Hakan Yildiz, John Hershberger, Subhash Suri
2011	J	`jnl`	Guest Editor's Foreword. Discret. Comput. Geom. John Hershberger
2011	J	`jnl`	Guest editors' foreword. ACM J. Exp. Algorithmics Irene Finocchi, John Hershberger
2011	A*	`conf`	On the Complexity of Time-Dependent Shortest Paths. SODA Luca Foschini, John Hershberger, Subhash Suri
2011	—	`conf`	Stable snap rounding. SCG John Hershberger
2011	A	`conf`	The Union of Probabilistic Boxes: Maintaining the Volume. ESA Hakan Yildiz, Luca Foschini, John Hershberger, Subhash Suri
2010	A*	`conf`	Road Network Reconstruction for Organizing Paths. SODA Daniel Chen, Leonidas J. Guibas, John Hershberger, Jian Sun
2009	—	`ed.`	Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, June 8-10, 2009 SCG John Hershberger, Efi Fogel
2009	A	`ed.`	Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, ALENEX 2009, New York, New York, USA, January 3, 2009 ALENEX Irene Finocchi, John Hershberger
2008	J	`jnl`	Adaptive sampling for geometric problems over data streams. Comput. Geom. John Hershberger, Subhash Suri
2008	J	`jnl`	Improved Output-Sensitive Snap Rounding. Discret. Comput. Geom. John Hershberger
2008	—	`conf`	Simplified Planar Coresets for Data Streams. SWAT John Hershberger, Subhash Suri
2008	J	`jnl`	Summarizing spatial data streams using ClusterHulls. ACM J. Exp. Algorithmics John Hershberger, Nisheeth Shrivastava, Subhash Suri
2007	—	`conf`	Approximate isocontours and spatial summaries for sensor networks. IPSN Sorabh Gandhi, John Hershberger, Subhash Suri
2007	J	`jnl`	Finding the ACM Trans. Algorithms John Hershberger, Matthew Maxel, Subhash Suri
2007	J	`jnl`	On the difficulty of some shortest path problems. ACM Trans. Algorithms John Hershberger, Subhash Suri, Amit M. Bhosle
2007	—	`conf`	Sparse data aggregation in sensor networks. IPSN Jie Gao, Leonidas J. Guibas, Nikola Milosavljevic, John Hershberger
2006	J	`jnl`	Adaptive Spatial Partitioning for Multidimensional Data Streams. Algorithmica John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth
2006	A*	`conf`	Cluster Hull: A Technique for Summarizing Spatial Data Streams. ICDE John Hershberger, Nisheeth Shrivastava, Subhash Suri
2006	B	`conf`	Contour Approximation in Sensor Networks. DCOSS Chiranjeeb Buragohain, Sorabh Gandhi, John Hershberger, Subhash Suri
2006	—	`conf`	Improved output-sensitive snap rounding. SCG John Hershberger
2006	A	`conf`	Summarizing Spatial Data Streams Using ClusterHulls. ALENEX John Hershberger, Nisheeth Shrivastava, Subhash Suri
2005	J	`jnl`	Binary Space Partitions of Orthogonal Subdivisions. SIAM J. Comput. John Hershberger, Subhash Suri, Csaba D. Tóth
2005	J	`jnl`	Geometric spanners for routing in mobile networks. IEEE J. Sel. Areas Commun. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
2005	J	`jnl`	Polygonal path simplification with angle constraints. Comput. Geom. Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Ningfang Mi, Jack Snoeyink
2005	J	`jnl`	Smooth kinetic maintenance of clusters. Comput. Geom. John Hershberger
2005	A*	`conf`	Space complexity of hierarchical heavy hitters in multi-dimensional data streams. PODS John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth
2004	A*	`conf`	Adaptive Sampling for Geometric Problems over Data Streams. PODS John Hershberger, Subhash Suri
2004	B	`conf`	Adaptive Spatial Partitioning for Multidimensional Data Streams. ISAAC John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth
2004	—	`conf`	Binary space partitions of orthogonal subdivisions. SCG John Hershberger, Subhash Suri, Csaba D. Tóth
2004	—	`conf`	Fractionally cascaded information in a sensor network. IPSN Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang
2004	J	`jnl`	Kinetic collision detection between two simple polygons. Comput. Geom. Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
2004	J	`jnl`	Kinetic collision detection with fast flight plan changes. Inf. Process. Lett. John Hershberger
2003	A*	`conf`	Binary space partitions for 3D subdivisions. SODA John Hershberger, Subhash Suri
2003	J	`jnl`	Discrete Mobile Centers. Discret. Comput. Geom. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
2003	A	`conf`	Finding the k Shortest Simple Paths: A New Algorithm and Its Implementation. ALENEX John Hershberger, Matthew Maxel, Subhash Suri
2003	A	`conf`	On the Difficulty of Some Shortest Path Problems. STACS John Hershberger, Subhash Suri, Amit M. Bhosle
2003	—	`conf`	Smooth kinetic maintenance of clusters. SCG John Hershberger
2002	J	`jnl`	Algorithmic issues in modeling motion. ACM Comput. Surv. 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
2002	J	`jnl`	Deformable Free-Space Tilings for Kinetic Collision Detection. Int. J. Robotics Res. Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang
2002	A*	`conf`	Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?". FOCS John Hershberger, Subhash Suri
2001	—	`conf`	Discrete mobile centers. SCG Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
2001	B	`conf`	Geometric spanner for routing in mobile networks. MobiHoc Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
2001	J	`jnl`	Guest Editor's Foreword - Selected Papers from the Fourteenth ACM Symposium on Computational Geometry, Minneapolis, Minnesota, June 1998. Int. J. Comput. Geom. Appl. John Hershberger
2001	J	`jnl`	Kinetic Connectivity for Unit Disks. Discret. Comput. Geom. Leonidas J. Guibas, John Hershberger, Subhash Suri, Li Zhang
2001	J	`jnl`	Maintaining the Extent of a Moving Point Set. Discret. Comput. Geom. Pankaj K. Agarwal, Leonidas J. Guibas, John Hershberger, Eric Veach
2001	A*	`conf`	Polygonal path approximation with angle constraints. SODA Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Jack Snoeyink
2001	A*	`conf`	Simplified kinetic connectivity for rectangles and hypercubes. SODA John Hershberger, Subhash Suri
2001	A*	`conf`	Vickrey Prices and Shortest Paths: What is an Edge Worth?. FOCS John Hershberger, Subhash Suri
2000	—	`conf`	Kinetic connectivity for unit disks. SCG Leonidas J. Guibas, John Hershberger, Subhash Suri, Li Zhang
2000	J	`jnl`	Lower Bounds for Kinetic Planar Subdivisions. Discret. Comput. Geom. Pankaj K. Agarwal, Julien Basch, Mark de Berg, Leonidas J. Guibas, John Hershberger
2000	J	`jnl`	Morphing Simple Polygons. Discret. Comput. Geom. Leonidas J. Guibas, John Hershberger, Subhash Suri
1999	J	`jnl`	An Optimal Algorithm for Euclidean Shortest Paths in the Plane. SIAM J. Comput. John Hershberger, Subhash Suri
1999	J	`jnl`	Data Structures for Mobile Data. J. Algorithms Julien Basch, Leonidas J. Guibas, John Hershberger
1999	A*	`conf`	Kinetic Collision Detection Between Two Simple Polygons. SODA Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
1999	—	`conf`	Kinetic Connectivity of Rectangles. SCG John Hershberger, Subhash Suri
1999	—	`conf`	Kinetic Data Structures: Animating Proofs Through Time. SCG Julien Basch, João Comba, Leonidas J. Guibas, John Hershberger, Craig Silverstein, Li Zhang
1999	—	`conf`	Lower Bounds for Kinetic Planar Subdivisions. SCG Pankaj K. Agarwal, Julien Basch, Mark de Berg, Leonidas J. Guibas, John Hershberger
1998	J	`jnl`	Cartographic line simplification and polygon CSG formulæ in O(nlog * n) time. Comput. Geom. John Hershberger, Jack Snoeyink
1998	J	`jnl`	Erased arrangements of lines and convex decompositions of polyhedra. Comput. Geom. John Hershberger, Jack Snoeyink
1998	J	`jnl`	Practical methods for approximating shortest paths on a convex polytope in R3. Comput. Geom. John Hershberger, Subhash Suri
1997	B	`conf`	Cartographic Line Simplification and Polygon CSG Formulae and in O(n log* n) Time. WADS John Hershberger, Jack Snoeyink
1997	A*	`conf`	Data Structures for Mobile Data. SODA Julien Basch, Leonidas J. Guibas, John Hershberger
1997	B	`conf`	Efficient Breakout Routing in Printed Circuit Boards (Extended Abstract). WADS John Hershberger, Subhash Suri
1997	—	`conf`	Efficient Breakout Routing in Printed Circuit Boards. SCG John Hershberger, Subhash Suri
1997	J	`jnl`	Finding a Shortest Diagonal of a Simple Polygon in Linear Time. Comput. Geom. John Hershberger, Subhash Suri
1997	B	`conf`	Maintaining the Extent of a Moving Point Set. WADS Pankaj K. Agarwal, Leonidas J. Guibas, John Hershberger, Eric Veach
1997	J	`jnl`	Matrix Searching with the Shortest-Path Metric. SIAM J. Comput. John Hershberger, Subhash Suri
1997	—	`conf`	Snap Rounding Line Segments Efficiently in Two and Three Dimensions. SCG Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tanenbaum
1996	J	`jnl`	Efficiently Planning Compliant Motion in the Plane. SIAM J. Comput. Joseph Friedman, John Hershberger, Jack Snoeyink
1996	J	`jnl`	Off-Line Maintenance of Planar Configurations. J. Algorithms John Hershberger, Subhash Suri
1995	J	`jnl`	A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk. J. Algorithms John Hershberger, Subhash Suri
1995	A*	`conf`	Morphing Binary Trees. SODA John Hershberger, Subhash Suri
1995	J	`jnl`	Optimal parallel algorithms for triangulated simple polygons. Int. J. Comput. Geom. Appl. John Hershberger
1995	A*	`conf`	Practical Methods for Approximating Shortest Paths on a Convex Polytope in R SODA John Hershberger, Subhash Suri
1995	A	`conf`	The Centroid of Points with Approximate Weights. ESA Marshall W. Bern, David Eppstein, Leonidas J. Guibas, John Hershberger, Subhash Suri, Jan Wolter
1994	—	`conf`	An Efficient Solution to the Zookeeper's Problem. CCCG John Hershberger, Jack Snoeyink
1994	—	`conf`	An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification. SCG John Hershberger, Jack Snoeyink
1994	J	`jnl`	Computing Minimum Length Paths of a Given Homotopy Class. Comput. Geom. John Hershberger, Jack Snoeyink
1994	J	`jnl`	Data Structures for Two-Edge Connectivity in Planar Graphs. Theor. Comput. Sci. John Hershberger, Monika Rauch, Subhash Suri
1994	—	`conf`	Morphing Simple Polygons. SCG Leonidas J. Guibas, John Hershberger
1994	J	`jnl`	Ray Shooting in Polygons Using Geodesic Triangulations. Algorithmica Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, John Hershberger, Micha Sharir, Jack Snoeyink
1994	J	`jnl`	Selecting Heavily Covered Points. SIAM J. Comput. Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir
1993	J	`jnl`	A Faster Algorithm for the Two-Center Decision Problem. Inf. Process. Lett. John Hershberger
1993	A*	`conf`	A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk. SODA John Hershberger, Subhash Suri
1993	J	`jnl`	An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon. Algorithmica David P. Dobkin, Leonidas J. Guibas, John Hershberger, Jack Snoeyink
1993	J	`jnl`	Approximating Polygons and Subdivisions with Minimum Link Paths. Int. J. Comput. Geom. Appl. Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, Jack Snoeyink
1993	—	`conf`	Compliant Motion in a Simple Polygon. SCG John Hershberger
1993	J	`jnl`	Computing the Intersection-Depth of Polyhedra. Algorithmica David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri
1993	A*	`conf`	Efficient Computation of Euclidean Shortest Paths in the Plane FOCS John Hershberger, Subhash Suri
1993	A*	`conf`	Matrix searching with the shortest path metric. STOC John Hershberger, Subhash Suri
1992	J	`jnl`	Applications of a Semi-Dynamic Convex Hull Algorithm. BIT John Hershberger, Subhash Suri
1992	J	`jnl`	Color and Sound in Algorithmic Animation. Computer Marc H. Brown, John Hershberger
1992	—	`conf`	Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra. SWAT John Hershberger, Jack Snoeyink
1992	—	`conf`	Fully Dynamic 2-Edge-Connectivity in Planar Graphs. SWAT John Hershberger, Monika Rauch, Subhash Suri
1992	J	`jnl`	Minimizing the Sum of Diameters Efficiently. Comput. Geom. John Hershberger
1992	—	`conf`	Optimal Parallel Algorithms for Triangulated Simple Polygons. SCG John Hershberger
1992	J	`jnl`	Upper Envelope Onion Peeling. Comput. Geom. John Hershberger
1991	J	`jnl`	A New Data Structure for Shortest Path Queries in a Simple Polygon. Inf. Process. Lett. John Hershberger
1991	—	`conf`	Approximating Polygons and Subdivisions with Minimum Link Paths. ISA Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, Jack Snoeyink
1991	—	`conf`	Color and Sound in Algorithm Animation. VL Marc H. Brown, John Hershberger
1991	J	`jnl`	Compact interval trees: a data structure for convex hulls. Int. J. Comput. Geom. Appl. Leonidas J. Guibas, John Hershberger, Jack Snoeyink
1991	B	`conf`	Computing Minimum Length Paths of a Given Homotopy Class (Extended Abstract). WADS John Hershberger, Jack Snoeyink
1991	J	`jnl`	Finding Tailored Partitions. J. Algorithms John Hershberger, Subhash Suri
1991	A*	`conf`	Offline Maintenance of Planar Configurations. SODA John Hershberger, Subhash Suri
1991	A*	`conf`	Ray Shooting in Polygons Using Geodesic Triangulations. ICALP Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, John Hershberger, Micha Sharir, Jack Snoeyink
1990	—	`conf`	Applications of a Semi-Dynamic Convex Hull Algorithm. SWAT John Hershberger, Subhash Suri
1990	A*	`conf`	Compact Interval Trees: A Data Structure for Convex Hulls. SODA Leonidas J. Guibas, John Hershberger, Jack Snoeyink
1990	—	`conf`	Implicitly Searching Convolutions and Computing Depth of Collision. SIGAL International Symposium on Algorithms David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri
1990	—	`conf`	Input-Sensitive Compliant Motion in the Plane. SWAT Joseph Friedman, John Hershberger, Jack Snoeyink
1990	—	`conf`	Slimming Down by Adding: Selecting Heavily Covered Points. SCG Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir
1990	—	`conf`	Sweeping Arrangements of Curves. Discrete and Computational Geometry Jack Snoeyink, John Hershberger
1990	—	`conf`	Upper Envelope Onion Peeling. SWAT John Hershberger
1989	J	`jnl`	An Optimal Visibility Graph Algorithm for Triangulated Simple Polygons. Algorithmica John Hershberger
1989	—	`conf`	Compliant Motion in a Simple Polygon. SCG Joseph Friedman, John Hershberger, Jack Snoeyink
1989	—	`conf`	Finding Tailored Partitions. SCG John Hershberger, Subhash Suri
1989	J	`jnl`	Finding the Upper Envelope of n Line Segments in O(n log n) Time. Inf. Process. Lett. John Hershberger
1989	J	`jnl`	Implicitly Representing Arrangements of Lines or Segments. Discret. Comput. Geom. Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, Emo Welzl
1989	J	`jnl`	On Arrangement of Jordan Arcs with Three Intersection per Pair. Discret. Comput. Geom. Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink
1989	J	`jnl`	Optimal Shortest Path Queries in a Simple Polygon. J. Comput. Syst. Sci. Leonidas J. Guibas, John Hershberger
1989	—	`conf`	Sweeping Arrangements of Curves. SCG Jack Snoeyink, John Hershberger
1988	J	`jnl`	An O(n²) Shortest Path Algorithm for a Non-Rotating Convex Body. J. Algorithms John Hershberger, Leonidas J. Guibas
1988	A*	`conf`	An efficient algorithm for finding the CSG representation of a simple polygon. SIGGRAPH David P. Dobkin, Leonidas J. Guibas, John Hershberger, Jack Snoeyink
1988	—	`conf`	Implicitly Representing Arrangements of Lines or Segments. SCG Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, Emo Welzl
1988	—	`conf`	On Arrangements of Jordan Arcs with Three Intersections per Pair. SCG Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink
1987	—	`—`	Efficient algorithms for shortest path and visibility problems. John Hershberger
1987	—	`conf`	Finding the Visibility Graph of a Simple Polygon in Time Proportional to its Size. SCG John Hershberger
1987	J	`jnl`	Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons. Algorithmica Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan
1987	—	`conf`	Optimal Shortest Path Queries in a Simple Polygon. SCG Leonidas J. Guibas, John Hershberger
1986	—	`conf`	Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons. SCG Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan
1986	J	`jnl`	Visibility of Disjoint Polygons. Algorithmica Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai
1985	J	`jnl`	A polynomial time algorithm for finding the prime factors of cartesian-product graphs. Discret. Appl. Math. Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer
1985	J	`jnl`	Computing the visibility graphs of n line segments in O(n Bull. EATCS Leonidas J. Guibas, John Hershberger
1985	A*	`conf`	Visibility-Polygon Search and Euclidean Shortest Paths FOCS Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai