Kinetic Data Structures: Animating Proofs Through Time (2009)
Julien Basch, João Comba, Leonidas J. Guibas, John Hershberger
Kinetic Data Structures (KDS for short) are a new class of data structures aimed at keeping track of attributes of interest in systems of moving objects [1, 2]. In this video we illustrate the...
Contour Approximation in Sensor Networks Chiranjeeb Buragohain 1, Sorabh Gandhi 1, (2008)
John Hershberger, Subhash Suri
Abstract. We propose a distributed scheme called Adaptive-Group-Merge forsensornetworksthat,givenaparameterk, approximates a geometric shape by a k-vertex polygon. The algorithm is well suited to the...
Cluster Hull: A Technique for Summarizing Spatial Data Streams (2008)
Recently there has been a growing interest in detecting patterns and analyzing trends in data that are generated continuously, often delivered in some fixed order and at a rapid rate, in the form of...
Abstract Efficient Computation of Euclidean Shortest Paths in the Plane (2008)
We propose a new algorithm for a classical problem in plane computational geometry: computing a short-est path between two points in the presence of polyg-onal obstacles. Our algorithm runs in...
Abstract Summarizing Spatial Data Streams Using ClusterHulls ∗ (2008)
John Hershberger, Nisheeth Shrivastava, Subhash Suri
We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional points, how can we summarize its spatial distribution or shape using a small, bounded amount of...
John Hershberger, Subhash Suri
Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful...
University of Pennsylvania (2008)
Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, John Hershberger, Christian Jensen, ...
DIMITRIS METAXAS
Jie Gao, Leonidas J. Guibas, John Hershberger, Ý Li Zhang, Þ An Zhu
We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm, RDG can be used as an underlying graph for geographic routing...
Contour Approximation in Sensor Networks Chiranjeeb Buragohain 1, Sorabh Gandhi 1, (2008)
John Hershberger, Subhash Suri
Abstract. We propose a distributed scheme called Adaptive-Group-Merge for sensor networks that, given a parameter k, approximates a geometric shape by a k-vertex polygon. The algorithm is well suited...
Pankaj K Agarwal, Julien Basch, Leonidas J Guibas, John Hershberger, Li Zhang, Pankaj K. Agarwal, ...
We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume...
Abstract Geometric Spanner for Routing in Mobile Networks (2008)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm, RDG can be used as an underlying graph for geographic routing...
Michael T Goodrich, John Hershberger, Leonidas J. Guibast
We study the problem of robustly rounding a set S of n line segments in R2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called “hot,...
Abstract Discrete Mobile Centers (2008)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Kinetic Data Structures: Animating Proofs Through Time (2008)
Julien Basch, João Comba, Leonidas J. Guibas, John Hershberger
Kinetic Data Structures (KDS for short) are a new class of data structures aimed at keeping track of attributes of interest in systems of moving objects [1,2]. In this video we illustrate the...
The Second Annual Video Review of Computational Geometry (2007)
Edited Marc, John Hershberger (eds.), Marc H. Brown, John Hershberger, Robert W. Taylor
Computational geometry concepts are often easiest to understand visually, in terms of the geometric objects they manipulate. Indeed, most papers in the field rely on diagrams to communicate the...
Kinetic Data Structures: Animating Proofs Through Time (2007)
Julien Basch, Joao Comba, Leonidas J. Guibas, John Hershberger
ficate triangle verifies that one of its vertices is not on the convex hull. Altogether, the certificates from all levels of the recursion prove the correctness of the convex hull. # Duke University;...
Abstract Finding the k Shortest Simple Paths: A New Algorithm and its Implementation (2007)
John Hershberger, Matthew Maxel, Subhash Suri
We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed...
Roberto Tamassia, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...
The proposed research will be in the area of applied algorithms in both the sequential and parallel domains. The focus of this work will be on the design and testing of realistic algorithms for...
Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tanenbaum
We study the problem of robustly rounding a set S of n line segments in R 2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called...
www.csee.usf.edu/#eugene (2007)
Eugene Fink, Josh Johnson, John Hershberger
www.csee.usf.edu/#jhershbe Abstract-- We present an exchange system for trading complex nonstandard goods, such as used cars. We explain the representation of desirable purchases and sales, describe...
John Hershberger, Subhash Suri
Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful...
Space Complexity of Hierarchical Heavy Hitters (2005)
John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth
Heavy hitters, which are items occurring with frequency above a given threshold, are an important aggregation and summary tool when processing data streams or data warehouses. Hierarchical heavy...
Adaptive sampling for geometric problems over data streams (2004)
Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations,...
Binary space partitions of orthogonal subdivisions (2004)
John Hershberger, Mentor Graphics, Corp Sw, Boeckman Road
Abstract We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can...
Fractionally cascaded information in a sensor network (2004)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang
We address the problem of distributed information aggregation and storage in a sensor network, where queries can be injected anywhere in the network. The principle we propose is that a sensor should...
Binary space partitions of orthogonal subdivisions (2004)
John Hershberger, Subhash Suri, Csaba D. Tóth
We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined...
Adaptive Spatial Partitioning for Multidimensional Data Streams (2004)
John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth
We propose a space-efficient scheme for summarizing multidimensional data streams. Our sketch can be used to solve spatial versions of several classical data stream queries efficiently. For instance,...
Adaptive sampling for geometric problems over data streams (2004)
Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations,...
Fractionally cascaded information in a sensor network (2004)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang
We address the problem of distributed information aggregation and storage in a sensor network, where queries can be injected anywhere in the network. The principle we propose is that a sensor should...
Binary space partitions for 3d subdivisions (2003)
We consider the following question: Given a subdivision of space into n convex polyhedral cells, what is the worst-case complexity of a binary space partition (BSP) for the subdivision? We show that...
On the Difficulty of Some Shortest Path Problems (2003)
John Hershberger, Subhash Suri, Amit Bhosle
We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem:...
On the Difficulty of Some Shortest Path Problems (2003)
John Hershberger, Subhash Suri, Amit Bhosle
We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem:...
Multi-Attribute Exchange Market: Representation and Indexing of Orders (2003)
Eugene Fink, Josh Johnson, John Hershberger
We present an automated exchange for trading complex goods, such as used cars, which allows traders to describe desirable purchases and sales by multiple attributes. The developed exchange system...
On the Difficulty of Some Shortest Path Problems (2003)
John Hershberger, Subhash Suri, Amit Bhosle
We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem:...
Multi-attribute exchange market: Theory and experiments (2003)
Eugene Fink, Josh Johnson, John Hershberger
Abstract. The Internet has opened opportunities for efficient on-line trading, and researchers have developed algorithms for various auctions, as well as exchanges for standardized commodities;...
Discrete Mobile Centers (2003)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Multi-Attribute Exchange Market: Theory and Experiments (2003)
Eugene Fink, Josh Johnson, John Hershberger
The Internet has opened opportunities for e#cient on-line trading, and researchers have developed algorithms for various auctions, as well as exchanges for standardized commodities; however, they...
Deformable free-space tilings for kinetic collision detection (2002)
Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang
We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume...
Erratum to “Vickrey prices and shortest paths: What is an edge worth (2002)
John Hershberger, Subhash Suri
the following replacement paths problem: Given a graph � with non-negative edge weights, and a pair of nodes Ü � Ý, let È � � � � ������Ô denote the sequence of edges in a...
Geometric Spanner for Routing in Mobile Networks (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
Abstract—We propose a new routing graph, the restricted Delaunay graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for...
Discrete Mobile Centers (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Discrete Mobile Centers (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Vickrey prices and shortest paths: What is an edge worth (2001)
John Hershberger, Subhash Suri
We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to...
Discrete Mobile Centers (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Geometric Spanner for Routing in Mobile Networks (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm, RDG can be used as an underlying graph for geographic routing...
Vickrey Pricing in network routing: Fast payment computation (2001)
John Hershberger, Subhash Suri
Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful...
Geometric Spanner for Routing in Mobile Networks (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm, RDG can be used as an underlying graph for geographic routing...
Geometric Spanner for Routing in Mobile Networks (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new routing graph, the Restricted Delaunay Graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for geographic...
Discrete Mobile Centers (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Vickrey prices and shortest paths: What is an edge worth (2001)
We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to...
Geometric Spanner for Routing in Mobile Networks (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
Abstract — We propose a new routing graph, the Restricted Delaunay Graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for...
Discrete Mobile Centers (2001)
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the...
Deformable free space tilings for kinetic collision detection (2000)
Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang
We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also change continuously with time. We construct a...
Deformable free space tilings for kinetic collision detection (2000)
Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang
We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also vary continuously with time. Unlike classical...
Deformable Free Space Tilings for Kinetic Collision Detection (2000)
Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang
We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also vary continuously with time. Unlike classical...
Kinetic Connectivity for Unit Disks (2000)
Leonidas Guibas, John Hershberger, Subhash Suri, Li Zhang
We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be...
Kinetic connectivity for unit disks (2000)
Leonidas Guibas, John Hershberger, Subhash Suri, Li Zhang
We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be...
Deformable free space tilings for kinetic collision detection (2000)
Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang
We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also vary continuously with time. Unlike classical...
Lower bounds for kinetic planar subdivisions (1999)
Pankaj K. Agarwal, Julien Basch, Mark De Berg, Leonidas J. Guibas, John Hershberger
We revisit the notion of kinetic efficiency for non-canonically-defined discrete attributes of moving data, like binary space partitions and triangulations. Under reasonable computational models, we...
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
Kinetic connectivity of rectangles (1999)
John Hershberger, Subhash Suri
We develop a kinetic data structure (KDS) for maintaining the connectivity of a set of axis-aligned rectangles moving in the plane. In the kinetic framework, each rectangle is assumed to travel along...
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Je Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
Lower bounds for kinetic planar subdivisions (1999)
Pankaj K. Agarwal, Julien Basch, Mark De Berg, Leonidas J. Guibas, John Hershberger
k We revisit the notion of kinetic efficiency for noncanonically-defined discrete attributes of moving data, like binary space partitions and triangulations. Under very general computational models,...
Lower Bounds For Kinetic Planar Subdivisions (1999)
Pankaj K. Agarwal, Julien Basch, Mark De Berg, Leonidas J. Guibas, John Hershberger
We revisit the notion of kinetic eciency for non-canonically-dened discrete attributes of moving data, like binary space partitions and triangulations. Under very general computational models, we...
Kinetic Collision Detection Between Two Simple Polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
MS-9627683 and by U.S. Army Research Office MURI grant DAAH04-96-1-0013. z Computer Science Department, Stanford University, Stanford, CA 94305; guibas@cs.stanford.edu. Research partially supported...
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
Cartographic line simplification and polygon csg formul (1998)
John Hershberger, Correspondence Address, Jack Snoeyink, Jack Snoeyink
2
Data Structures for Mobile Data (1998)
Julien Basch, Leonidas J. Guibas, John Hershberger
A kinetic data structure (KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a conceptual framework for kinetic data...
Data structures for mobile data (1997)
Julien Basch, Leonidas J. Guibas, John Hershberger
A kinetic data structure (KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a conceptual framework for kinetic data...
Efficient breakout routing in printed circuit boards (1997)
John Hershberger, Subhash Suri
Abstract. Breakout routing is a single-layer wire-routing problem in which each of a set of pins must be connected to one of a set of vias, but no matching is prespecified. We propose a network-flow...
An Optimal Algorithm for Euclidean Shortest Paths in the Plane (1997)
John Hershberger, Subhash Suri
We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs...
Maintaining the Extent of a Moving Point Set (1997)
Pankaj K. Agarwal, Leonidas J. Guibas, John Hershberger, Eric Veach
Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of the...
Snap Rounding Line Segments Efficiently in Two and Three Dimensions (1997)
Michael Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tanenbaum
We study the problem of robustly rounding a set S of n line segments in R 2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called...
Strategic Directions in Computational Geometry (1996)
Roberto Tamassia, Roberto Tamassia (editor, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
The centroid of points with approximate weights (1995)
Marshall Bern, Leonidas Guibas, John Hershberger, Subhash Suri
3
Practical Methods for Approximating Shortest Paths on a Convex Polytope in R^3 (1995)
John Hershberger, Subhash Suri
We propose an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p; q...
John Hershberger, Subhash Suri
We investigate the problem of transforming one binary tree into another by rotations, subject to certain weight constraints on the nodes of the trees. These constraints arise in the problem of...
Computing minimum length paths of a given homotopy class (1994)
John Hershberger, Jack Snoeyink
In this paper, we show that the universal covering space of a surface can be used to unify previous results on computing paths in a simple polygon. We optimize a given path among obstacles in the...
Computing minimum length paths of a given homotopy class (1994)
Jack Snoeyik, John Hershberger, John Hershberger, Jack Snoeyink
the Netherlands t
The Third Annual Video Review of Computational Geometry (1994)
Edited Marc, John Hershberger (eds.), Marc H. Brown, John Hershberger, Robert W. Taylor
Computational geometry concepts are often easiest to understand visually, in terms of the geometric objects they manipulate. Indeed, most papers in the field rely on diagrams to communicate the...
Data Structures for Two-Edge Connectivity in Planar Graphs (1994)
John Hershberger, Monika Rauch, Subhash Suri
We present a data structure for maintaining 2-edge connectivity information dynamically in an embedded planar graph. The data structure requires linear storage and preprocessing time for its...
Separating Bi-Chromatic Points by Parallel Lines (1994)
Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri
Given a 2-coloring of the vertices of a regular n-gon P , how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that bn=2c is a tight upper bound, and also...
The Third Annual Video Review (1994)
Edited Marc, H. Brown, John Hershberger
The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support...
Animation of Geometric Algorithms: A Video Review (1993)
Edited Marc, John Hershberger (Eds.), Marc H. Brown, John Hershberger
Geometric algorithms and data structures are often easiest to understand visually, in terms of the geometric objects they manipulate. Indeed, most papers in computational geometry rely on diagrams to...
Matrix Searching with the Shortest Path Metric (1993)
John Hershberger, Subhash Suri
We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally-monotone n \Theta n matrix whose entries represent shortest-path distances between pairs of vertices...
Computing the Intersection-Depth of Polyhedra (1993)
David Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri
Given two intersecting polyhedra P , Q and a direction d, find the smallest translation of Q along d that renders the interiors of P and Q disjoint. The same problem can also be posed without...
101a The Second Annual Video Review of Computational Geometry (1993)
Edited Marc, H. Brown, John Hershberger
The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support...
Finding a shortest diagonal of a simple polygon in linear time (1993)
John Hershberger, Subhash Suri
Abstract A diagonal of a planar, simple polygon P is an open line segment that connects two non-adjacent vertices and lies in the relative interior of P. We present a linear time algorithm for...
Speeding Up the Douglas-Peucker Line-Simplification Algorithm (1992)
John Hershberger, Jack Snoeyink
We analyze the line simplification algorithm reported by Douglas and Peucker and show that its worst case is quadratic in n, the number of input points. Then we give a algorithm, based on path hulls,...
87a Animation of Geometric Algorithms: A Video Review (1992)
Edited Marc, H. Brown, John Hershberger
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
a Color and Sound in Algorithm Animation (1991)
Although systems for animating algorithms are becoming more powerful and easier for programmers to use, not enough attention has been given to the techniques that an algorithm animator needs to...
76a Color and Sound in Algorithm Animation (1991)
Marc H. Brown, John Hershberger
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Separating Bi-Chromatic Points by Parallel Lines (1990)
Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri
Given a 2-coloring of the vertices of a regular n-gon P, how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that ⌊n/2 ⌋ is a tight upper bound, and...
An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon (1989)
David Dobkin, Leonidas Guibas, John Hershberger, Jack Snoeyink
Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the...
the CSG Representation of a Simple Polygon �... (1989)
David Dobkin, Leonidas Guibas, John Hershberger, Jack Snoeyink
ii
Data Structures for Mobile Data
Julien Basch, Leonidas J. Guibas, John Hershberger
this paper come primarily from computational geometry and are motivated by problems like collision detection in robotics or animation, visibility determination in computer graphics, etc. Our...
Data Structures for Mobile Data
Julien Basch, Leonidas J. Guibas, John Hershberger
this paper come primarily from computational geometry and are motivated by problems like collision detection in robotics or animation, visibility determination in computer graphics, etc. Our...