Pankaj K. Agarwal, Herbert Edelsbrunner (pi, Homme W. Hellinga, Leonidas J. Guibas, ...
The function of all life forms depends on organization in space and time, and the effect of one part of a biological system on another is generally much greater when the two parts are in close...
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...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled
We introduce two new related metrics, the geodesic width and the link width, for measuring the “distance ” between two non-intersecting polylines in the plane. If the two polylines have n...
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually \see " an evader that is unpredictable, has unknown initial position,...
Persistence-Based Clustering in Riemannian Manifolds (2009)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve, Skraba, Primoz
We present a novel clustering algorithm that combines a mode-seeking phase with a cluster merging phase. While mode detection is performed by a standard graph-based hill-climbing scheme, the novelty...
Persistence-Based Clustering in Riemannian Manifolds (2009)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve, Skraba, Primoz
We present a novel clustering algorithm that combines a mode-seeking phase with a cluster merging phase. While mode detection is performed by a standard graph-based hill-climbing scheme, the novelty...
Robust Voronoi-based Curvature and Feature Estimation (2009)
Mérigot, Quentin, Ovsjanikov, Maks, Guibas, Leonidas J.
Many algorithms for shape analysis and shape processing rely on accurate estimates of differential information such as normals and curvature. In most settings, however, care must be taken around...
Robust Voronoi-based Curvature and Feature Estimation (2009)
Mérigot, Quentin, Ovsjanikov, Maks, Guibas, Leonidas J.
Many algorithms for shape analysis and shape processing rely on accurate estimates of differential information such as normals and curvature. In most settings, however, care must be taken around...
Structural Bioinformatics Persistent voids: a new structural metric for membrane fusion (2008)
Peter M. Kasson, Afra Zomorodian, Sanghyun Park, Nina Singhal, Leonidas J. Guibas, Vijay S. P
Motivation: Membrane fusion constitutes a key stage in cellular processes such as synaptic neurotransmission and infection by enveloped viruses. Current experimental assays for fusion have thus far...
1 Introduction Acting Locally but Thinking Globally (2008)
Department of Computer Science,
Probabilistic roadmap planners have been used with success to plan paths for flexible objects such as metallic plates or plastic flexible pipes. This paper improves the performance of these planners...
S. K. Abdali, G. W. Cherry, Alok Aggarwal, Leonidas J. Guibas, James Saxe, Alfred V. Aho, ...
[2] Habib Abdulrab and Jean-Pierre P'ecuchet. Solving word equations. In Claude Kirchner,
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
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...
Gunnar Carlsson, Anne Collins, Leonidas J. Guibas
Communicated by (xxxxxxxxxx) In this paper, we initiate a study of shape description and classification via the application of persistent homology to tangential constructions on geometric objects....
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir
A singly exponential stratification scheme for real semi-algebraic varieties and its applications*
Huijia Lin, Maohua Lu, Leonidas J. Guibas, Nikola Milosavljević
In sensor networks we aim to achieve global objectives through local decisions at each node, based only on data available in the node’s neighborhood. In this paper, we diffuse information away from...
The Stability of Persistence Diagrams Revisited (2008)
Chazal, Frédéric, Cohen-Steiner, David, Guibas, Leonidas J., Oudot, Steve
The concept of topological persistence introduced independently by several groups \cite{elz-tps-02,r-tchfa-99,f-dcsf-92} is a rather general tool providing an efficient way to encode the qualitative...
The Stability of Persistence Diagrams Revisited (2008)
Chazal, Frédéric, Cohen-Steiner, David, Guibas, Leonidas J., Oudot, Steve
The concept of topological persistence introduced independently by several groups \cite{elz-tps-02,r-tchfa-99,f-dcsf-92} is a rather general tool providing an efficient way to encode the qualitative...
Abstract Sweeping Lines and Line Segments with a Heap (2008)
Julien Basch, Leonidas J. Guibas
Given n line segments in the plane, the Bentley-Ottmann sweep maintains the exact ordering of the intersections of the segments with a vertical line, as this line sweeps the plane from left to right....
Julien Basch, Leonidas J. Guibas
We presentasetofnovel data structures for the e cient maintenance of various attributes of mobile data. For example, given n points continuously moving in the plane, we give methods for maintaining...
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...
ABSTRACT Deformable Spanners and Applications (2008)
Jie Gao, Leonidas J. Guibas, An Nguyen
For a set S of points in R d,ans-spanner is a graph on S such that any pair of points is connected via some path in the spanner whose total length is at most s times the Euclidean distance between...
SELECTINGHEAVILYCOVEREDPOINTS* (2008)
Herbert Edelsbrunnert, Leonidas J. Guibas, John E, Hershberger Raimund, Seidel Ii, Micha Sharir
Abstract. A collection ofgeometric selection lemmas is proved, such as the following: Forany set P ofn points in three-dimensional space and any set,9 ofm spheres, where each sphere passes through a...
Symmetry Extraction Pipeline. (2008)
Niloy J. Mitra, Cluster Height, Leonidas J. Guibas
locally symmetrized globally symmetrized Approximate Symmetry Detection and Symmetrization SYMMETRY DETECTION: Natural and man-made objects often exhibit symmetry and contain repeated structures. We...
Abstract Proximity Problems on Moving Points (2008)
Julien Basch, Leonidas J. Guibas, Li Zhang
A kinetic data structure for the maintenance of a multidimensional range search treeisintroduced. This structure is used as a building block to obtain kinetic data structures for two classical...
Peter M. Kasson, Afra Zomorodian, Sanghyun Park, Nina Singhal, Leonidas J. Guibas, Vijay S. P
Motivation: Membrane fusion constitutes a key stage in cellular processes such as synaptic neurotransmission and infection by enveloped viruses. Current experimental assays for fusion have thus far...
Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks (2008)
An Nguyen, Nikola Milosavljević, Qing Fang, Jie Gao, Leonidas J. Guibas
Abstract—We study the problem of landmark selection for landmark-based routing in a network of fixed wireless communication nodes. We present a distributed landmark selection algorithm that does...
Motion is ubiquitous in the physical world, yet its study is much less developed than that of another common physical modality, namely shape. While we have several standardized mathematical shape...
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...
Discrete and computational geometry (2008)
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P. We provide a mechanism for expressing the visibility polygon from a point as the...
Learning Smooth Shapes by Probing (2008)
Jean-daniel Boissonnat, Leonidas J. Guibas, Steve Oudot
We consider the problem of discovering a smooth unknown surface S bounding an object O in R 3. The discovery process consists of moving a point probing device in the free space around O so that it...
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...
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...
Motion is ubiquitous in the physical world, yet its study is much less developed than that of another common physical modality, namely shape. While we have several standardized mathematical shape...
Distance-Sensitive Information Brokerage in Sensor Networks (2008)
Stefan Funke, Leonidas J. Guibas, An Nguyen, Yusu Wang
Abstract. In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of...
Robust Global Registration (2008)
M. Desbrun, H. Pottmann (editors, Natasha Gelfand, Niloy J. Mitra, Leonidas J. Guibas
We present an algorithm for the automatic alignment of two 3D shapes (data and model), without any assumptions about their initial positions. The algorithm computes for each surface point a...
Shape Segmentation Using Local Slippage Analysis Abstract (2008)
R. Scopigno, D. Zorin, Natasha Gelf, Leonidas J. Guibas
We propose a method for segmentation of 3D scanned shapes into simple geometric parts. Given an input point cloud, our method computes a set of components which possess one or more slippable motions:...
Distance-Sensitive Information Brokerage in Sensor Networks (2008)
Stefan Funke, Leonidas J. Guibas, Yusu Wang
Abstract. In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of...
Danny B. Yang, Leonidas J. Guibas, Ali Ozer Ercan
dbyang,jwshin,aliercan£ In this paper, we study how to task camera sensor nodes to reason about the occupancy of the area around them. Occupancy information is valuable because it can be used to...
Abstract Cylindrical Static and Kinetic Binary Space Partitions (2008)
Pankaj K. Agarwal, Leonidas J. Guibas
We describe the rst known algorithm for e ciently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show that...
Kinetic Medians and ��-Trees (2008)
Pankaj K. Agarwal, Leonidas J. Guibas
Abstract. We propose algorithms for maintaining two variants of ��-trees of a set of moving points in the plane. A pseudo ��-tree allows the number of points stored in the two children to...
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 Union of Moving Polygonal Pseudodiscs { Combinatorial Bounds and Applications (2008)
Mark Berg, Hazel Everett, Leonidas J. Guibas
Let P be a set of polygonal pseudodiscs in the plane with n edges in total translating with xed velocities in xed directions. We prove that the maximum number of combinatorial changes in the union of...
Danny B. Yang, Leonidas J. Guibas, Ali Ozer Ercan
dbyang,jwshin,aliercan£ In this paper, we study how to task camera sensor nodes to reason about the occupancy of the area around them. Occupancy information is valuable because it can be used to...
Electronic Imaging: Science (2008)
Leonidas J. Guibas, Brian Rogo, Carlo Tomasi
IS&T/SPIE Symposium on
Analysis of Scalar Fields over Point Cloud Data (2008)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve Y., Skraba, Primoz
Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L of sample...
Analysis of Scalar Fields over Point Cloud Data (2008)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve Y., Skraba, Primoz
Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L of sample...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Analysis of Scalar Fields over Point Cloud Data (2008)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve Y., Skraba, Primoz
Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L of sample...
Analysis of Scalar Fields over Point Cloud Data (2008)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve Y., Skraba, Primoz
Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L of sample...
Leonidas J. Guibas, Steve Y. Oudot, Jie Gao, Yue Wang
We introduce a new feature size for bounded domains in the plane endowed with an intrinsic metric. Given a point x in a domain X, the homotopy feature size of X at x measures half the length of the...
Analysis of Scalar Fields over Point Cloud Data (2008)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve Y., Skraba, Primoz
Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L of sample...
Analysis of Scalar Fields over Point Cloud Data (2008)
Chazal, Frédéric, Guibas, Leonidas J., Oudot, Steve Y., Skraba, Primoz
Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L of sample...
Arvo James Arvo, Bare Gill Barequet, Bernard Chazelle, Leonidas J. Guibas, Joseph S. B, ...
surfaces in 3d. Computer Graphics Forum, 15(3):387–396, August 1996. [Barn86] J. E. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(6270):446–449, 1986....
Interval Methods for Kinetic Simulations (2007)
Leonidas J. Guibas, Menelaos I. Karavelas
We propose a speed-up method for discrete-event simulations, including sweep-line or-plane techniques, requiring the repeated calculation of the times at which certain discrete events occur. Instead...
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;...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, T. M. Murali
We introduce two new related metrics, the geodesic width and the link width, for measuring the \distance " between two non-intersecting polylines in the plane. If the two polylines have n...
Pankaj K. Agarwal, Leonidas J. Guibas, T. M. Murali, Jeffrey Scott Vitter
We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show...
Leonidas J. Guibas, John E. Hershberger, Jack Scott Snoeyink
Communicated by Editor's name We study several variations on one basic approach to the task of simplifying a plane polygon or subdivision: Fatten the given object and construct an approximation...
Probabilistic roadmap planners have been used with success to plan paths for flexible objects such as metallic plates or plastic flexible pipes. This paper improves the performance of these planners...
Mark De Berg, Hazel Everett, Leonidas J. Guibas
Let P be a set of polygonal pseudodiscs in the plane with n edges in total translating with fixed velocities in fixed directions. We prove that the maximum number of combinatorial changes in the...
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...
Leonidas J. Guibas, Dan Halperin, Hirohisa Hirukawa, Jean-claude Latombe, Randall H. Wilson
We study the following problem: given a collection of polyhedral parts in 3D, determine whether there is a subset of the parts that can be moved as a rigid body by an infinitesimal translation and...
Staying in the Middle: Exact and Approximate Medians in R (2007)
And For Moving, Pankaj K. Agarwal, Mark De Berg, Jie Gao, Leonidas J. Guibas, ...
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies \in the middle" of a given point set. We study several fundamental problems of this...
Persistent voids: a new structural metric for membrane fusion (2007)
Kasson, Peter M., Zomorodian, Afra, Park, Sanghyun, Singhal, Nina, Guibas, Leonidas J., Pande, Vijay S.
Motivation: Membrane fusion constitutes a key stage in cellular processes such as synaptic neurotransmission and infection by enveloped viruses. Current experimental assays for fusion have thus far...
Manifold reconstruction in arbitrary dimensions using witness complexes (2007)
Jean-daniel Boissonnat, Leonidas J. Guibas, Steve Y. Oudot
It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex...
Object tracking in the presence of occlusions via a camera network (2007)
Ali Ozer Ercan, Leonidas J. Guibas
This paper describes a sensor network approach to tracking a single object in the presence of static and moving occluders using a network of cameras. To conserve communication bandwidth and energy,...
Reconstruction using witness complexes (2007)
Leonidas J. Guibas, Steve Y. Oudot
We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a one-parameter family of complexes that approximate S at different scales. At a high...
CS268: Geometric Algorithms Handout # 3 Design and Analysis (2007)
Motion is ubiquitous in the physical world, yet its study is much less developed than that of another common physical modality, namely shape. While we have several standardized mathematical shape...
A package for exact kinetic data structures and sweepline algorithms (2007)
Daniel Russel, Menelaos I. Karavelas, Leonidas J. Guibas
In this paper we present a package for implementing exact kinetic data structures built on objects which move along polynomial trajectories. We discuss how the package design was influenced by...
Geometric Approaches to Ad Hoc and Sensor Networks: Full Report of the 2006 NSF Workshop (2006)
Subhash Suri, Alon Efrat, Leonidas J. Guibas
Embedded networked sensing devices are becoming ubiquitous across many activities that are important to our economy and life, from manufacturing and industrial sensing, to agriculture and...
M.: Partial and approximate symmetry detection for 3d geometry (2006)
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly
Figure 1: Symmetry detection on a sculpted model. From left to right: Original model, detected partial and approximate symmetries, color-coded deviations from perfect symmetry as a fraction of the...
Distance-sensitive routing and information brokerage in sensor networks (2006)
Stefan Funke, Leonidas J. Guibas, An Nguyen, Yusu Wang
Abstract — In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of...
M.: Partial and approximate symmetry detection for 3d geometry (2006)
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly
Figure 1: Symmetry detection on a sculpted model. From left to right: Original model, detected partial and approximate symmetries, color-coded deviations from perfect symmetry as a fraction of the...
L.J.: Locating and bypassing holes in sensor networks (2006)
Qing Fang, Jie Gao, Leonidas J. Guibas
In real sensor network deployments, spatial distributions of sensors are usually far from being uniform. Such networks often contain regions without enough sensor nodes, which we call holes. In this...
Landmark-based information storage and retrieval in sensor networks (2006)
Qing Fang, Jie Gao, Leonidas J. Guibas
Abstract — For a wide variety of sensor network environments, location information is unavailable or expensive to obtain. We propose a location-free, lightweight, distributed, and data-centric...
Optimal placement and selection of camera network nodes for target localization (2006)
Ali O. Ercan, Danny B. Yang, Abbas El Gamal, Leonidas J. Guibas
Abstract. The paper studies the optimal placement of multiple cameras and the selection of the best subset of cameras for single target localization in the framework of sensor networks. The cameras...
05381 Executive Summary -- Form and Content in Sensor Networks (2006)
Guibas, Leonidas J., Hanebeck, Uwe D., Henderson, Thomas C.
From the September 18th until September 23rd, 2005 a Dagstuhl Seminar took place with the topic "Form and Content in Sensor Networks". 26 participants from four different countries, which are experts...
05381 Abstracts Collection -- Form and Content in Sensor Networks (2006)
Guibas, Leonidas J., Hanebeck, Uwe D., Henderson, Thomas C.
From 18.09.05 to 23.09.05, the Dagstuhl Seminar 05381 ``Form and Content in Sensor Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the...
Efficient raytracing of deforming point-sampled surfaces (2005)
Keiser, Richard, Pauly, Mark, Guibas, Leonidas J., Gross, Marcus
We present efficient data structures and caching schemes to accelerate ray-surface intersections for deforming point-sampled surfaces. By exploiting spatial and temporal coherence of the deformation...
Distributed proximity maintenance in ad hoc mobile networks (2005)
Jie Gao, Leonidas J. Guibas, An Nguyen
Abstract. We present an efficient distributed data structure, called the D-SPANNER, for maintaining proximity information among communicating mobile nodes. The D-SPANNER is a kinetic sparse graph...
Distributed proximity maintenance in ad hoc mobile networks (2005)
Jie Gao, Leonidas J. Guibas, An Nguyen
We present an efficient distributed data structure, called the D-SPANNER, for maintaining proximity information among communicating mobile nodes. The D-SPANNER is a kinetic sparse graph spanner on...
Efficient Collision Detection Among Moving Spheres with Unknown Trajectories (2005)
Ho Kyung Kim, Leonidas J. Guibas, Sung Yong Shin
Abstract. Collision detection is critical for applications that demand a great deal of spatial interaction among objects. In such applications the trajectory of an object is often not known in...
Efficient raytracing of deforming pointsampled surfaces (2005)
Bart Adams, Richard Keiser, Mark Pauly, Leonidas J. Guibas, Markus Gross, Philip Dutré
We present efficient data structures and caching schemes to accelerate ray-surface intersections for deforming point-sampled surfaces. By exploiting spatial and temporal coherence of the deformation...
GLIDER: Gradient landmark-based distributed routing for sensor networks (2005)
Qing Fang, Jie Gao, Leonidas J. Guibas, Vin Silva, Li Zhang
Routing (GLIDER), a novel naming/addressing scheme and associated routing algorithm, for a network of wireless communicating nodes. We assume that the nodes are fixed (though their geographic...
Efficient raytracing of deforming pointsampled surfaces (2005)
Bart Adams, Richard Keiser, Mark Pauly, Leonidas J. Guibas, Markus Gross, Philip Dutré
We present efficient data structures and caching schemes to accelerate ray-surface intersections for deforming point-sampled surfaces. By exploiting spatial and temporal coherence of the deformation...
Learning Surfaces by Probing (2004)
Boissonnat, Jean-Daniel, Guibas, Leonidas J., Oudot, Steve
We consider the problem of discovering a smooth unknown surface S bounding an object O in R^3. The discovery process consists of moving a point probing device in the free space around O so that it...
Learning Surfaces by Probing (2004)
Boissonnat, Jean-Daniel, Guibas, Leonidas J., Oudot, Steve
We consider the problem of discovering a smooth unknown surface S bounding an object O in R^3. The discovery process consists of moving a point probing device in the free space around O so that it...
Deformable spanners and applications (2004)
Jie Gao, Leonidas J. Guibas, An Nguyen
For a set S of points in R d,ans-spanner is a graph on S such that any pair of points is connected via some path in the spanner whose total length is at most s times the Euclidean distance between...
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...
Deformable spanners and applications (2004)
Jie Gao, Leonidas J. Guibas, An Nguyen
For a set S of points in R d, an s-spanner is a subgraph of the complete graph with node set S such that any pair of points is connected via some path in the spanner whose total length is at most s...
Uncertainty and Variability in Point Cloud Surface Data (2004)
M. Alexa, S. Rusinkiewicz (editors, Mark Pauly, Niloy J. Mitra, Leonidas J. Guibas
We present a framework for analyzing shape uncertainty and variability in point-sampled geometry. Our representation is mainly targeted towards discrete surface data stemming from 3D acquisition...
Quasi-Rigid Objects in Contact (2004)
R. Boulic, Mark Pauly, Dinesh K. Pai, Leonidas J. Guibas
We investigate techniques for modeling contact between quasi-rigid objects -- solids that undergo modest deformation in the vicinity of a contact, while the overall object still preserves its basic...
Deformable spanners and applications (2004)
Jie Gao, Leonidas J. Guibas, An Nguyen
For a set S of points in R d, an s-spanner is a graph on S such that any pair of points is connected via some path in the spanner whose total length is at most s times the Euclidean distance between...
ALGORITHMS EXPLOITING THE CHAIN STRUCTURE OF PROTEINS (2004)
Jean-claude Latombe, Leonidas J. Guibas
ii I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a disser-tation for the degree of Doctor of Philosophy.
Roamhba: maintaining group connectivity in sensor networks (2004)
Qing Fang, Jie Liu, Leonidas J. Guibas, Feng Zhao
Abstract. This paper presents a new group communication scheme arises from collaborative information processing in wireless sensor networks, roamingcast. Roamingcast enables communication among a...
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...
Spanning Trees Crossing Few Barriers (2003)
Asano, Tetsuo, De Berg, Mark, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao
We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...
Staying in the Middle: Exact and Approximate Medians (2003)
In R, Pankaj K. Agarwaly, Mark Bergz, Jie Gaox, Leonidas J. Guibas, ...
Jaewon Shin, Leonidas J. Guibas, Feng Zhao
Abstract. This paper presents a scalable distributed algorithm for computing and maintaining multi-target identity information. The algorithm builds on a novel representational framework,...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...
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...
Counting people in crowds with a real-time network of simple image sensors (2003)
Danny B. Yang, Leonidas J. Guibas
Estimating the number of people in a crowded environment is a central task in civilian surveillance. Most vision-based counting techniques depend on detecting individuals in order to count, an...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
We study the problem of “staying in the middle”: we have a set of points moving in a geometric space and wish to maintain another point (possibly one of the given points, but not necessarily)...
Kinetic Medians and kd-Trees (2002)
Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas
We propose algorithms for maintaining two variants of kd- trees of a set of moving points in the plane. A pseudo kd-tree allows the number of points stored in the two children to di#er by a constant...
Kinetic medians and kd-trees (2002)
Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas
Abstract. We propose algorithms for maintaining two variants of kd-trees of a set of moving points in the plane. A pseudo kd-tree allows the number of points stored in the two children to differ. An...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, T. M. Murali
We introduce two new related metrics, the geodesic width and the link width, for measuring the “distance ” between two non-intersecting polylines in the plane. If the two polylines have n...
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...
Static and kinetic geometric spanners with applications (2001)
Menelaos I. Karavelas, Leonidas J. Guibas
It is well known that the Delaunay Triangulation is a spanner graph of its vertices. In this paper we show that any bounded aspect ratio triangulation in two and three dimensions is a spanner graph...
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...
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...
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...
Static and kinetic geometric spanners with applications (2001)
Menelaos I. Karavelas, Leonidas J. Guibas
It is well known that the Delaunay Triangulation is a spanner graph of its vertices. In this paper we show that any bounded aspect ratio triangulation in two and three dimensions is a spanner graph...
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...
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...
Disconnection proofs for motion planning (2001)
Julien Basch, Leonidas J. Guibas, David Hsu, An Thai Nguyen
Probabilistic road-map (PRM) planners have shown great promise in attacking motion planning problems with many degrees of freedom that were previously infeasible. Yet when such a planner fails 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...
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...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
Abstract We consider the problem of locating a continuously-moving target using a group of guardsmoving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
Abstract We consider the problem of locating a moving target using a group of guards cooperatively moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon...
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...
On incremental rendering of silhouette maps of a polyhedral scene (2000)
Alon Efrat, Leonidas J. Guibas, Li Zhang
We consider the problem of incrementally rendering a polyhedral scene while the viewpoint is moving. In practical situations the number of geometric primitives to be rendered can be very large---...
Penetration depth of two convex polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Sweeping Simple Polygons with a Chain of Guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin, T. M. Murali
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Penetration depth of two convex polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Sweeping Simple Polygons with a Chain of Guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin, T. M. Murali
We consider the problem of locating a moving target using a group of guards cooperatively moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Morphing between Polylines (2000)
Alon Efrat, Sariel Har-peled, Leonidas J. Guibas, T. M. Murali
We study the problem of continuously transforming or morphing two non-intersecting simple (not self-intersecting) polylines in the plane. Our morphing strategies have the property that every...
Computing the Penetration Depth of Two Convex Polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that 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...
The earth mover’s distance as a metric for image retrieval (2000)
Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas
1 Introduction Multidimensional distributions are often used in computer vision to describe and summarize different features of an image. For example, the one-dimensional distribution of image...
The earth mover’s distance as a metric for image retrieval (2000)
Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas
We introduce a metric between two distributions that we call the Earth Mover's Distance (EMD). The EMD is based on the minimal cost that must be paid to transform one distribution into 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 vary continuously with time. Unlike classical...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm) (1999)
Asano, Tetsuo, Berg, Mark De, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao
Emerging Challenges in Computational Topology (1999)
Bern, Marshall, Eppstein, David, Agarwal, Pankaj K., Amenta, Nina, Chew, Paul, Dey, Tamal, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...
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...
Spanning trees crossing few barriers (1999)
Tetsuo Asano, Mark Berg Cheong, Leonidas J. Guibas, Jack Snoeyink, Hisao Tamaki
We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a...
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,...
A Visibility-Based Pursuit-Evasion Problem (1999)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see " an evader that is unpredictable, has unknown initial...
H-Walk : Hierarchical Distance Computation for Moving Convex Bodies (1999)
Leonidas J. Guibas, David Hsu, Li Zhang
This paper presents the Hierarchical Walk, or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For...
Leonidas J. Guibas, Christopher Holleman, Lydia E. Kavraki
Probabilistic roadmap planners have been used with success to plan paths for flexible objects such as metallic plates or plastic flexible pipes. This paper improves the performance of these planners...
Separation-Sensitive Collision Detection for Convex Objects (1999)
Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during...
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 Data Structures (1999)
Julien Basch, Leonidas J. Guibas
Modeling the physical world in the computer raises problems that intertwine discrete and continuous aspects. For example, physical objects move along continuous trajectories; yet every so often...
Lizhangg Cs Stanford, Leonidas J. Guibas, David Hsu, Li Zhang
This paper presents the Hierarchical Walk, or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For...
H-Walk: Hierarchical Distance Computation for Moving Convex Bodies (1999)
Leonidas J. Guibas, David Hsu, Li Zhang
This paper presents the Hierarchical Walk, or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For...
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...
Separation-Sensitive Collision Detection for Convex Objects (1998)
Erickson, Jeff, Guibas, Leonidas J., Stolfi, Jorge, Zhang, Li
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during...
Parametric and kinetic minimum spanning trees (1998)
Agarwal, Pankaj K., Eppstein, David, Guibas, Leonidas J., Henzinger, Monika R.
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter, and wish to computethe sequence of minimum spanning...
Adaptive color-image embedding for database navigation (1998)
Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas
Abstract. We present anovel approach to the problem of navigating through a database of color images for the purpose of image retrieval. We endow the database with a metric for the color...
Euclidean proximity and power diagrams (1998)
Power diagrams [Aur87] are a useful generalization of Voronoi diagrams in which the sites defining the diagram are not points but balls. They derive their name
Parametric and Kinetic Minimum Spanning Trees (1998)
Pankaj Agarwal David, Leonidas J. Guibas, Monika R. Henzinger
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter # and wish to compute the sequence of minimum...
Parametric and Kinetic Minimum Spanning Trees (1998)
Pankaj Agarwal, David Eppstein, Leonidas J. Guibas, Monika R. Henzinger
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter # and wish to compute the sequence of minimum...
Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (1998)
Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas
) Pankaj K. Agarwal Jeff Erickson y Leonidas J. Guibas z Abstract We describe randomized algorithms for efficiently maintaining a binary space partition of continuously moving, possibly intersecting,...
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...
Euclidean Proximity and Power Diagrams (1998)
this paper, we don't assume nondegeneracy. Thus, it is possible that two power diagram cells share a low dimensional face but not a facet. In this case, we don't regard them as adjacent in...
Visibility Queries in Simple Polygons and Applications (1998)
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P . We provide a mechanism for expressing the visibility polygon from a point as...
A metric for distributions with applications to image databases (1998)
Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas
We introduce a new distance between two distributions that we call the Earth Mover’s Distance (EMD), which reflects the minimal amount of work that must be performed to transform one...
Adaptive color-image embedding for database navigation (1998)
Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas
Abstract. We present anovel approach to the problem of navigating through a database of color images for the purpose of image retrieval. We endow the database with a metric for the color...
Visibility queries in simple polygons and applications (1998)
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
Abstract. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon §. We provide a mechanism for expressing the visibility polygon from a...
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...
Proximity problems on moving points (1997)
Julien Basch, Leonidas J. Guibas, Li Zhang
A kinetic data structure for the maintenance of a multidimensional range search tree is introduced. This structure is used as a building block to obtain kinetic data structures for two classical...
Cylindrical static and kinetic binary space partitions (1997)
Pankaj K. Agarwal, Leonidas J. Guibas, T. M. Murali, Jeffrey Scott Vitter
We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane, whose interiors remain disjoint throughout the...
A Practical Evaluation of Kinetic Data Structures (1997)
Julien Basch, Leonidas J. Guibas, Craig D. Silverstein, Li Zhang
this paper is to study and validate the use of the kinetic data structures proposed in [BGH97] in practice. The implementation and experimental evaluation of such structures brings to light several...
Metropolis Light Transport (1997)
Eric Veach, Leonidas J. Guibas
We present a new Monte Carlo method for solving the light transport problem, inspired by the Metropolis sampling method in computational physics. To render an image, we generate a sequence of light...
A Practical Evaluation of Kinetic Data Structures (1997)
Julien Basch, Leonidas J. Guibas, Craig D. Silverstein, Li Zhang
this paper, we reported the implementation of and experimentation with several data structures for maintaining the
The Earth Mover's Distance: Lower Bounds and Invariance under Translation (1997)
Scott D. Cohen, Leonidas J. Guibas
The Earth Mover's Distance #EMD# between two #nite distributions of weight is proportional to the minimum amountofwork required to transform one distribution into the other. Current...
Partial Matching of Planar Polylines Under Similarity Transformations (1997)
Scott D. Cohen, Leonidas J. Guibas
Given two planar polylines T and P with n and m edges, respectively, we present an O(m 2 n 2 ) time, O(mn) space algorithm to find portions of the "text" T which are similar in shape to the...
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...
Finding an Unpredictable Target in a Workspace with Obstacles (1997)
Steven M. Lavalle, David Lin, Leonidas J. Guibas, Jean-claude Latombe, Rajeev Motwani
This paper introduces a visibility-based motion planning problem in which the task is to coordinate the motions of one or more robots that have omnidirectional vision sensors, to eventually...
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...
Visibility-Based Pursuit-Evasion in a Polygonal Environment (1997)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see" an evader that is unpredictable, has unknown initial position,...
Shape-based Image Retrieval Using Geometric Hashing (1997)
Scott D. Cohen, Leonidas J. Guibas
We present a general strategy for shape-based image retrieval which considers similarity modulo a given transformation group G. The shape content of an image is summarized by recording what geometric...
Proximity Problems on Moving Points (1997)
Julien Basch, Leonidas J. Guibas, Li Zhang
A kinetic data structure for the maintenance of a multidimensional range search tree is introduced. This structure is used as a building block to obtain kinetic data structures for two classical...
Finding an Unpredictable Target in a Workspace with Obstacles (1997)
Steven Lavalle, David Lin, Leonidas J. Guibas, Jean-claude Latombe, Rajeev Motwani
This paper introduces a visibility-based motion planning problem in which the task is to coordinate the motions of one or more robots that have omnidirectional vision sensors, to eventually...
Sweeping Lines and Line Segments with a Heap (1997)
Julien Basch, Leonidas J. Guibas, G. D. Ramkumar
Given n line segments in the plane, the Bentley-Ottmann sweep maintains the exact ordering of the intersections of the segments with a vertical line, as this line sweeps the plane from left to right....
Proximity Problems on Moving Points (1997)
Julien Basch, Leonidas J. Guibas, Li Zhang
A kinetic data structure for the maintenance of a multidimensional range search tree is introduced. This structure is used as a building block to obtain kinetic data structures for two classical...
The earth mover’s distance: Lower bounds and invariance under translation (1997)
Scott D. Cohen, Leonidas J. Guibas
The Earth Mover's Distance (EMD) between two nite distributions of weight is proportional to the minimum amount ofwork required to transform one distribution into the other. Current...
Metropolis light transport (1997)
Eric Veach, Leonidas J. Guibas
We present a new Monte Carlo method for solving the light transport problem, inspired by the Metropolis sampling method in computational physics. To render an image, we generate a sequence of light...
The exact fitting problem in higher dimensions (1996)
Leonidas J. Guibas, Leonidas J. Guibas, Jean-marc Robert, Jean-marc Robert, Jean-marc Robert, I Leonidas, ...
Let S be a family of n points in E a. The exact fitting problem asks for finding a hyperplane containing the maximum number of points of $. In this paper, we present an O (rain j ' "...
Image retrieval and robot vision research at Stanford (1996)
Leonidas J. Guibas, Carlo Tomasi
We report on the two areas of our research that are sponsored by ARPA, namely, the retrieval of images from data bases and vision for mobile robots. In image retrieval, we have developed two demos....
Polyhedral Tracings and their Convolution (1996)
Julien Basch, Leonidas J. Guibas, G. D. Ramkumar, Lyle Ramshaw
Polyhedral Tracings and their Convolution (1996)
Julien Basch, Leonidas J. Guibas, G. D. Ramkumar, Lyle Ramshaw
this paper is to define the notion of polyhedral tracings, which extends the classical notion of a polyhedron in exactly the same way a polygonal tracing extends the notion of a polygon. We also...
A Visibility-Based Pursuit-Evasion Problem (1996)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see" an evader that is unpredictable, has unknown initial position,...
Polyhedral Tracings and their Convolution (1996)
Julien Basch, Leonidas J. Guibas, G. D. Ramkumar, Lyle Ramshaw
this paper is to define the notion of polyhedral tracings, which extends the classical notion of a polyhedron in exactly the same way a polygonal tracing extends the notion of a polygon. We also...
A Visibility-Based Pursuit-Evasion Problem (1996)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper presents a visibility-based motion planning problem in which the task is to coordinate the motions of one or more robots that have omnidirectional vision sensors, to eventually...
Shape-based Illustration Indexing and Retrieval Some First Steps (1996)
Scott Cohen, Leonidas J. Guibas
We propose a general set of ideas for indexing technical illustrations based on the shapes present in them, so that they can be efficiently retrieved later using as the key other...
Reporting Red-Blue Intersections Between Two Sets Of Connected Line Segments (1996)
Julien Basch, Leonidas J. Guibas, G. D. Ramkumar
. We present a new line sweep algorithm, HeapSweep, for reporting bichromatic (`purple') intersections between a red and a blue family of line segments. If the union of the segments in each...
Discrete Geometric Shapes: Matching, Interpolation, and Approximation: A Survey (1996)
Helmut Alt, Leonidas J. Guibas
In this survey we consider geometric techniques which have been used to measure the similarity or distance between shapes, as well as to approximate shapes, or interpolate between shapes. Shape is a...
Shape-based illustration indexing and retrieval - some rst steps (1996)
Scott D. Cohen, Leonidas J. Guibas
We propose a general set of ideas for indexing technical illustrations based on the shapes present in them, so that they can be e ciently retrieved later using as the key other `similar-looking...
Image retrieval and robot vision research at Stanford (1996)
Leonidas J. Guibas, Carlo Tomasi
We report on the two areas of our research that are sponsored by ARPA, namely, the retrieval of images from data bases and vision for mobile robots. In image retrieval, we have developed two demos....
Shape-based illustration indexing and retrieval - some rst steps (1996)
Scott D. Cohen, Leonidas J. Guibas
We propose a general set of ideas for indexing technical illustrations based on the shapes present in them, so that they can be e ciently retrieved later using as the key other `similarlooking'...
BOXTREE: Hierarchical Representation for Surfaces in 3D (1996)
Gill Barequet, Bernard Chazelle, Leonidas J. Guibas, Ayellet Tal
We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing...
BOXTREE: A Hierarchical Representation for Surfaces in 3D (1996)
Gill Barequet, Bernard Chazelle, Leonidas J. Guibas, Ayellet Tal
We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing...
Reporting red-blue intersections between two sets of connected line segments (1996)
Julien Basch, Leonidas J. Guibas, G. D. Ramkumar
Abstract. We present a new line sweep algorithm, HeapSweep, for reporting bichromatic (`purple') intersections between a red and a blue family of line segments. If the union of the segments in...
Leonidas J. Guibas, Dan Halperin, Hirohisa Hirukawa, Jean-claude Latombe
We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an in nitesimal translation...
The Robot Localization Problem (1995)
Leonidas J. Guibas, Rajeev Motwani, Prabhakar Raghavan
We consider the following problem: given a simple polygon P and a star-shaped polygon V , find a point (or the set of points) in P from which the portion of P that is visible is translation-congruent...
Vertical Decompositions for Triangles in 3-Space (1995)
Mark De Berg, Leonidas J. Guibas, Dan Halperin
We prove that, for any constant " ? 0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n 2+" + K), where K is the complexity of the...
Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions (1995)
Leonidas J. Guibas, Dan Halperin, Jirí Matousek, Micha Sharir
We show that, for any collection H of n hyperplanes in ! 4 , the combinatorial complexity of the vertical decomposition of the arrangement A(H) of H is O(n 4 log n). The proof relies on properties of...
Leonidas J. Guibas, Dan Halperin, H. Hirukawa, J.C. Latombe, R.H. Wilson, Hirohisa Hirukawa, ...
We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal...
Vertical Decompositions for Triangles in 3-Space (1994)
Mark De Berg, Leonidas J. Guibas, Dan Halperin
We prove that, for any constant " ? 0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n 2+" + K), where K is the complexity of the...
Approximating Polygons and Subdivisions with Minimum-Link Paths (1991)
Leonidas J. Guibas, John E. Hershberger, Jack Scott Snoeyink
In the practical application of computers to graphics, image processing, and geographic information systems, one often wishes to replace complex geometric objects with simpler objects that capture...
Elsevier Counting and cutting cycles of lines and rods in space* (1991)
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, ...
306 B. Chazelle et al.
Fractional cascading: I. A data structuring technique (1986)
Bernard Chazelle, Leonidas J. Guibas
Abstract. In computational geometry many search problems and range queries can be solved by performing an iterative search for the same key in separate ordered lists. In this paper we show that, if...
Probabilistic analysis of a network resource allocation algorithm (1986)
Nancy A. Lynch, Michael J. Fischer, Nancy D. Griffeth, Leonidas J. Guibas, A Bstra Ct
Code] governs the making of photocopies or other reproductions of copyrighted material Under certain conditions specified in the law, libraries and archives are authorized to furnish a photocopy or...
Probabilistic analysis of a network resource allocation algorithm (1986)
Nancy A. Lynch, Nancy D. Griffeth, Michael J. Fischer, Leonidas J. Guibas
Code] governs the making of photocopies or other reproductions of copyrighted material Under certain conditions specified in the law, libraries and archives are authorized to furnish a photocopy or...
The analysis of hashing algorithms /--by Leonidas John Guibas. (1976)
Photocopy of typescript. Ann Arbor, Mich. : University Microfilms, 1980. -- 21 cm.
The analysis of hashing algorithms--[microform] /--by Leonidas John Guibas. (1976)
Thesis (Ph. D.)--Stanford University, 1976.
Separation-Sensitive Collision Detection for Convex Objects
Je Erickson Leonidas, Leonidas J. Guibas, Jorge Stol, Li Zhang
this paper, see http://www:uiuc:edu/ph/www/jee/pubs/kollide:html.
Voronoi Diagrams of Moving Points
Gerhard Albers, Leonidas J. Guibas, Thomas Roos
Consider a set of n points in d-dimensional Euclidean space, d 2, each of which is continuously moving along a given individual trajectory. At each instant in time, the points define a Voronoi...
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...
Separation-Sensitive Collision Detection for Convex Objects
Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang
this paper, see http://www:uiuc:edu/ph/www/jee/pubs/kollide:html.