Bio


Professor Guibas heads the Geometric Computation group in the Computer Science Department of Stanford University and is a member of the Computer Graphics and Artificial Intelligence Laboratories. He works on algorithms for sensing, modeling, reasoning, rendering, and acting on the physical world. Guibas interests span computational geometry, geometric modeling, computer graphics, computer vision, sensor networks, robotics, and discrete algorithms --- all areas in which he has published and lectured extensively. Current foci of interest include geometric modeling with point cloud data, deformations and contacts, organizing and searching libraries of 3D shapes and images, sensor networks for lightweight distributed estimation / reasoning, analysis of GPS traces and other mobility data, and modeling the shape and motion biological macromolecules and other biological structures. More theoretical work is aimed at investigating fundamental computational issues and limits in geometric computing and modeling.

Honors & Awards


  • Fellow, ACM (1999)
  • Allen Newell Award, ACM (2008)
  • Fellow, IEEE (2011)
  • Member, National Academy of Engineering (2017)
  • Member, National Academy of Arts and Sciences (2018)

Professional Education


  • PhD, Stanford University (1976)
  • MS, California Institute of Technology (1971)
  • BS, California Institute of Technology (1971)

Current Research and Scholarly Interests


Geometric and topological data analysis and machine learning. Algorithms for the joint analysis of collections of images, 3D models, or trajectories. 3D reconstruction.

2023-24 Courses


Stanford Advisees


Graduate and Fellowship Programs


  • Biomedical Informatics (Phd Program)

All Publications


  • From Planes to Corners: Multi-Purpose Primitive Detection in Unorganized 3D Point Clouds RA-Letters Sommer, C., Sun, Y., Guibas, L. J., Cremers, D., Birdal, T. 2020; 5: 8

    View details for DOI 10.1109/LRA.2020.2969936

  • Synchronizing Probability Measures on Rotations via Optimal Transport IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Birdal, T., Arbel, M., Simsekli, U., Guibas, L. 2020: 1566–76
  • Learning Multiview 3D Point Cloud Registration IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Gojcic, Z., Zhou, C., Wegner, J. D., Guibas, L. J., Birdal, T. 2020: 1756–66
  • Shape Matching via Quotient Spaces COMPUTER GRAPHICS FORUM Ovsjanikov, M., Merigot, Q., Patraucean, V., Guibas, L. 2013; 32 (5): 1-11

    View details for DOI 10.1111/cgf.12167

    View details for Web of Science ID 000323204000001

  • Consistent Shape Maps via Semidefinite Programming COMPUTER GRAPHICS FORUM Huang, Q., Guibas, L. 2013; 32 (5): 177-186

    View details for DOI 10.1111/cgf.12184

    View details for Web of Science ID 000323204000018

  • Dirichlet Energy for Analysis and Synthesis of Soft Maps COMPUTER GRAPHICS FORUM Solomon, J., Guibas, L., Butscher, A. 2013; 32 (5): 197-206

    View details for DOI 10.1111/cgf.12186

    View details for Web of Science ID 000323204000020

  • Map-Based Exploration of Intrinsic Shape Differences and Variability ACM TRANSACTIONS ON GRAPHICS Rustamov, R. M., Ovsjanikov, M., Azencot, O., Ben-Chen, M., Chazal, F., Guibas, L. 2013; 32 (4)
  • Building Markov state models with solvent dynamics 11th Asia Pacific Bioinformatics Conference (APBC) Gu, C., Chang, H., Maibaum, L., Pande, V. S., Carlsson, G. E., Guibas, L. J. BIOMED CENTRAL LTD. 2013

    Abstract

    Markov state models have been widely used to study conformational changes of biological macromolecules. These models are built from short timescale simulations and then propagated to extract long timescale dynamics. However, the solvent information in molecular simulations are often ignored in current methods, because of the large number of solvent molecules in a system and the indistinguishability of solvent molecules upon their exchange.We present a solvent signature that compactly summarizes the solvent distribution in the high-dimensional data, and then define a distance metric between different configurations using this signature. We next incorporate the solvent information into the construction of Markov state models and present a fast geometric clustering algorithm which combines both the solute-based and solvent-based distances.We have tested our method on several different molecular dynamical systems, including alanine dipeptide, carbon nanotube, and benzene rings. With the new solvent-based signatures, we are able to identify different solvent distributions near the solute. Furthermore, when the solute has a concave shape, we can also capture the water number inside the solute structure. Finally we have compared the performances of different Markov state models. The experiment results show that our approach improves the existing methods both in the computational running time and the metastability.In this paper we have initiated an study to build Markov state models for molecular dynamical systems with solvent degrees of freedom. The methods we described should also be broadly applicable to a wide range of biomolecular simulation analyses.

    View details for PubMedID 23368418

  • Graph Matching with Anchor Nodes: A Learning Approach CVPR2013 Hu, N., Rustamov, Raif, M., Guibas, L. 2013
  • Locating Lucrative Passengers for Taxicab Drivers. Tang, H., Kerber, M., Huang, Q., Guibas, L. 2013
  • Large-Scale Joint Map Matching of GPS Traces Li, Y., Huang, Q., Kerber, M., Zhang, L., Guibas, L. 2013
  • Image Co-Segmentation via Consistent Functional Maps. Wang, F., Huang, Q., Guibas, L. 2013
  • Wavelets on Graphs via Deep Learning NIPS Rustamov, Raif, M., Guibas, L. 2013
  • Pathlet Learning for Compressing and Planning Trajectories. Chen, C., Su, H., Huang, Q., Zhang, L., Guibas, L. 2013
  • Guided Real-Time Scanning of Indoor Environments, Computer Graphics Forum Kim, Y., Mitra, N., Huang, Q., Guibas, Leonidas, J. 2013
  • Guided Real-Time Scanning of Indoor Environments Computer Graphics Forum, Pacific Graphics Kim, Y., Mitra, N., Huang, Q., Guibas, Leonidas, J. 2013
  • Acquiring 3D Indoor Environments with Variability and Repetition ACM TRANSACTIONS ON GRAPHICS Kim, Y. M., Mitra, N. J., Yan, D., Guibas, L. 2012; 31 (6)
  • Microtiles: Extracting Building Blocks from Correspondences COMPUTER GRAPHICS FORUM Kalojanov, J., Bokeloh, M., Wand, M., Guibas, L., Seidel, H., Slusallek, P. 2012; 31 (5): 1597-1606
  • Functional Maps: A Flexible Representation of Maps Between Shapes ACM TRANSACTIONS ON GRAPHICS Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., Guibas, L. 2012; 31 (4)
  • Detecting Network Cliques with Radon Basis Pursuit. Jiang, X., Yao, Y., Liu, H., Guibas, L. 2012
  • Supervised Earth Mover's Distance Learning and its Computer Vision Applications Wang, F., Guibas, L. 2012
  • Joint Shape Segmentation with Linear Programming ACM TRANSACTIONS ON GRAPHICS Huang, Q., Koltun, V., Guibas, L. 2011; 30 (6)
  • A Condition Number for Non-Rigid Shape Matching COMPUTER GRAPHICS FORUM Ovsjanikov, M., Huang, Q., Guibas, L. 2011; 30 (5): 1503-1512
  • An Optimization Approach to Improving Collections of Shape Maps COMPUTER GRAPHICS FORUM Andy Nguyen, A., Ben-Chen, M., Welnicka, K., Ye, Y., Guibas, L. 2011; 30 (5): 1481-1491
  • As-Killing-As-Possible Vector Fields for Planar Deformation COMPUTER GRAPHICS FORUM Solomon, J., Ben-Chen, M., Butscher, A., Guibas, L. 2011; 30 (5): 1543-1552
  • Probabilistic Reasoning for Assembly-Based 3D Modeling ACM TRANSACTIONS ON GRAPHICS Chaudhuri, S., Kalogerakis, E., Guibas, L., Koltun, V. 2011; 30 (4)
  • Exploration of Continuous Variability in Collections of 3D Shapes ACM TRANSACTIONS ON GRAPHICS Ovsjanikov, M., Li, W., Guibas, L., Mitra, N. J. 2011; 30 (4)
  • Discovery of Intrinsic Primitives on Triangle Meshes COMPUTER GRAPHICS FORUM Solomon, J., Ben-Chen, M., Butscher, A., Guibas, L. 2011; 30 (2): 365-374
  • Overcomplete Radon Bases for Target Property Management in Sensor Networks. Jiang, X., Li, M., Yao, Y., Guibas, L. 2011
  • Data- driven trajectory smoothing. Chazal, F., Chen, D., Guibas, L., Jiang, X., Sommer, C. 2011
  • A Fourier-Theoretic Approach for Inferring Symmetries. Jiang, X., Sun, J., Guibas, L. 2011
  • Persistence-based clustering in riemannian manifolds. Chazal, F., Guibas, Leonidas, J., Oudot, Steve, Y., Skraba, P. 2011
  • Kinetically-aware Conformational Distances in Molecular Dynamics. Gu, C., Jiang, X., Guibas, L. 2011
  • Metric Graph Reconstruction from Noisy Data 27th Annual ACM Symposium on Computational Geometry Aanjaneya, M., Chazal, F., Chen, D., Glisse, M., Guibas, L., Morozov, D. ASSOC COMPUTING MACHINERY. 2011: 37–46
  • Human Action Recognition by Learning Bases of Action Attributes and Parts IEEE International Conference on Computer Vision (ICCV) Yao, B., Jiang, X., Khosla, A., Lin, A. L., Guibas, L., Li Fei-Fei, F. F. IEEE. 2011: 1331–1338
  • Fourier-Information Duality in the Identity Management Problem European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) Jiang, X., Huang, J., Guibas, L. SPRINGER-VERLAG BERLIN. 2011: 97–113
  • Network Warehouses: Efficient Information Distribution to Mobile Users IEEE INFOCOM Conference Motskin, A., Downes, I., Kusy, B., Gnawali, O., Guibas, L. IEEE. 2011: 2069–2077
  • Witnessed k-Distance 27th Annual ACM Symposium on Computational Geometry Guibas, L., Merigot, Q., Morozov, D. ASSOC COMPUTING MACHINERY. 2011: 57–64
  • Geodesic Patterns ACM TRANSACTIONS ON GRAPHICS Pottmann, H., Huang, Q., Deng, B., Schiftner, A., Kilian, M., Guibas, L., Wallner, J. 2010; 29 (4)
  • One Point Isometric Matching with the Heat Kernel COMPUTER GRAPHICS FORUM Ovsjanikov, M., Merigot, Q., Memoli, F., Guibas, L. 2010; 29 (5): 1555-1564
  • On Discrete Killing Vector Fields and Patterns on Surfaces COMPUTER GRAPHICS FORUM Ben-Chen, M., Butscher, A., Solomon, J., Guibas, L. 2010; 29 (5): 1701-1711
  • Image Webs: Computing and Exploiting Connectivity in Image Collections 23rd IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Heath, K., Gelfand, N., Ovsjanikov, M., Aanjaneya, M., Guibas, L. J. IEEE COMPUTER SOC. 2010: 3432–3439
  • Data Stashing: Energy-Efficient Information Delivery to Mobile Sinks through Trajectory Prediction. Lee, H., Wicke, M., Kusy, B., Gnawali, O., Guibas, L. 2010
  • Persistence-based Segmentation of Deformable Shapes, 3rd Workshop on Non-Rigid Shape Analysis and Deformable Image Alignment Skraba, P., Ovsjanikov, M., Chazal, F., Guibas, L. 2010
  • Kinetic Stable Delaunay Graphs. Agarwal, Pankaj, K., Gao, J., Guibas, L., Kaplan, H., Koltun, V., Rubin, N. 2010
  • Constructing Multi-Resolution Markov State Models (MSMs)to Elucidate RNA Hairpin Folding Mechanisms. Huang, X., Yao, Y., Bowman, Gregory, R., Sun, J., Guibas, Leonidas, J., Carlsson, G. 2010
  • Meshless Shape and Motion Design for Multiple Deformable Objects COMPUTER GRAPHICS FORUM Adams, B., Wicke, M., Ovsjanikov, M., Wand, M., Seidel, H., Guibas, L. J. 2010; 29 (1): 43-59
  • Road Network Reconstruction for Organizing Paths 21st Annual ACM/SIAM Symposium on Discrete Algorithms Chen, D., Guibas, L. J., Hershberger, J., Sun, J. SIAM. 2010: 1309–1320
  • Robust Single-View Geometry and Motion Reconstruction ACM SIGGRAPH Asia Conference 2009 Li, H., Adams, B., Guibas, L. J., Pauly, M. ASSOC COMPUTING MACHINERY. 2009
  • Gromov-Hausdorff Stable Signatures for Shapes using Persistence 7th Eurographics Symposium on Geometry Processing (SGP) Chazal, F., Cohen-Steiner, D., Guibas, L. J., Memoli, F., Oudot, S. Y. WILEY-BLACKWELL. 2009: 1393–1403
  • Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes 23rd Annual Symposium on Computational Geometry Boissonnat, J., Guibas, L. J., Oudot, S. Y. SPRINGER. 2009: 37–70
  • A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion 7th Eurographics Symposium on Geometry Processing (SGP) Sun, J., Ovsjanikov, M., Guibas, L. WILEY-BLACKWELL. 2009: 1383–92
  • Topological methods for exploring low-density states in biomolecular folding pathways JOURNAL OF CHEMICAL PHYSICS Yao, Y., Sun, J., Huang, X., Bowman, G. R., Singh, G., Lesnick, M., Guibas, L. J., Pande, V. S., Carlsson, G. 2009; 130 (14)

    Abstract

    Characterization of transient intermediate or transition states is crucial for the description of biomolecular folding pathways, which is, however, difficult in both experiments and computer simulations. Such transient states are typically of low population in simulation samples. Even for simple systems such as RNA hairpins, recently there are mounting debates over the existence of multiple intermediate states. In this paper, we develop a computational approach to explore the relatively low populated transition or intermediate states in biomolecular folding pathways, based on a topological data analysis tool, MAPPER, with simulation data from large-scale distributed computing. The method is inspired by the classical Morse theory in mathematics which characterizes the topology of high-dimensional shapes via some functional level sets. In this paper we exploit a conditional density filter which enables us to focus on the structures on pathways, followed by clustering analysis on its level sets, which helps separate low populated intermediates from high populated folded/unfolded structures. A successful application of this method is given on a motivating example, a RNA hairpin with GCAA tetraloop, where we are able to provide structural evidence from computer simulations on the multiple intermediate states and exhibit different pictures about unfolding and refolding pathways. The method is effective in dealing with high degree of heterogeneity in distribution, capturing structural features in multiple pathways, and being less sensitive to the distance metric than nonlinear dimensionality reduction or geometric embedding methods. The methodology described in this paper admits various implementations or extensions to incorporate more information and adapt to different settings, which thus provides a systematic tool to explore the low-density intermediate states in complex biomolecular folding systems.

    View details for DOI 10.1063/1.3103496

    View details for Web of Science ID 000265617200017

    View details for PubMedID 19368437

    View details for PubMedCentralID PMC2719471

  • Efficient Reconstruction of Nonrigid Shape and Motion from Real-Time 3D Scanner Data ACM TRANSACTIONS ON GRAPHICS Wand, M., Adams, B., Ovsjanikov, M., Berner, A., Bokeloh, M., Jenke, P., Guibas, L., Seidel, H., Schilling, A. 2009; 28 (2)
  • Shape Decomposition using Modal Analysis COMPUTER GRAPHICS FORUM Huang, Q., Wicke, M., Adams, B., Guibas, L. 2009; 28 (2): 407-416
  • Proximity of Persistence Modules and their Diagrams. Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L., J., Oudot, S., Y. 2009
  • ShapeGoogle: a computer vision approach for invariant shape retrieval Ovsjanikov, M., Bronstein, A., M., Bronstein, M., M., Guibas, L., J. 2009
  • Robust Voronoi-based Curvature and Feature Estimation Mérigot, Q., Ovsjanikov, M., Guibas, L. 2009
  • Dynamic Resource Management and Matching in Sensor Networks Gao, J., Guibas, L., Milosavljevic, N., Zhou, D. 2009
  • Analysis of Scalar Fields over Point Cloud Data. Chazal, F., Guibas, L., J., Oudot, S., Y., Skraba, P. 2009
  • Lightweight Coloring and Desynchronization for Networks IEEE INFOCOM Conference 2009 Motskin, A., Roughgarden, T., Skraba, P., Guibas, L. IEEE. 2009: 2383–2391
  • Predictive QoS Routing to Mobile Sinks in Wireless Sensor Networks 8th International Symposium on Information Processing Sensor Networks Kusy, B., Lee, H., Wicke, M., Milosavljevic, N., Guibas, L. IEEE. 2009: 109–120
  • Interference-Aware MAC Protocol for Wireless Networks by a Game-Theoretic Approach IEEE INFOCOM Conference 2009 Lee, H., Kwon, H., Motskin, A., Guibas, L. IEEE. 2009: 1854–1862
  • Reconstruction using witness complexes DISCRETE & COMPUTATIONAL GEOMETRY Guibas, L. J., Oudot, S. Y. 2008; 40 (3): 325-356

    Abstract

    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 level, our method is very similar in spirit to Chew's surface meshing algorithm, with one notable difference though: the restricted Delaunay triangulation is replaced by the witness complex, which makes our algorithm applicable in any metric space. To prove its correctness on curves and surfaces, we highlight the relationship between the witness complex and the restricted Delaunay triangulation in 2d and in 3d. Specifically, we prove that both complexes are equal in 2d and closely related in 3d, under some mild sampling assumptions.

    View details for DOI 10.1007/s00454-008-9094-6

    View details for Web of Science ID 000259563600002

    View details for PubMedCentralID PMC3105630

  • Discovering structural regularity in 3D geometry ACM SIGGRAPH Conference 2008 Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., Guibas, L. J. ASSOC COMPUTING MACHINERY. 2008
  • Structural insight into RNA hairpin folding intermediates JOURNAL OF THE AMERICAN CHEMICAL SOCIETY Bowman, G. R., Huang, X., Yao, Y., Sun, J., Carlsson, G., Guibas, L. J., Pande, V. S. 2008; 130 (30): 9676-?

    Abstract

    Hairpins are a ubiquitous secondary structure motif in RNA molecules. Despite their simple structure, there is some debate over whether they fold in a two-state or multi-state manner. We have studied the folding of a small tetraloop hairpin using a serial version of replica exchange molecular dynamics on a distributed computing environment. On the basis of these simulations, we have identified a number of intermediates that are consistent with experimental results. We also find that folding is not simply the reverse of high-temperature unfolding and suggest that this may be a general feature of biomolecular folding.

    View details for DOI 10.1021/ja8032857

    View details for Web of Science ID 000257902500027

    View details for PubMedID 18593120

    View details for PubMedCentralID PMC2652247

  • Global intrinsic symmetries of shapes 6th Eurographics Symposium on Geometry Processing (SGP 2008) Ovsjanikov, M., Sun, J., Guibas, L. WILEY-BLACKWELL. 2008: 1341–48
  • Non-rigid registration under isometric deformations 6th Eurographics Symposium on Geometry Processing (SGP 2008) Huang, Q., Adams, B., Wicke, M., Guibas, L. J. WILEY-BLACKWELL. 2008: 1449–57
  • Robust Extraction of 1D Skeletons from Grayscale 3D Images 19th International Conference on Pattern Recognition (ICPR 2008) Antunez, E., Guibas, L. IEEE. 2008: 2112–2115
  • Localization of Mobile Users Using Trajectory Matching. Lee, H., Wicke, M., Kusy, B., Guibas, L. 2008
  • Enabling data interpretation through user collaboration in sensor networks Cho, E., Wong, K., Kusy, B., Guibas, L. 2008
  • Bounded uncertainty roadmaps for path planning. Guibas, L., J., Hsu, D., Kurniawati, H., Rehman, E. 2008
  • Geodesic Delaunay Triangulation and Witness Complex in the Plane. Gao, J., Guibas, L., Oudot, S., Wang, Y. 2008
  • The Identity Management Problem — A Short Survey. Guibas, Leonidas, J. 2008
  • Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks Sarkar, R., Zhu, X., Gao, J., Guibas, Leonidas, J., Mitchell, Joseph, S. B. 2008
  • Composable Information Gradients in Wireless Sensor Networks Lin, H., Lu, M., Milosavljevic, N., Gao, J., Guibas, Leonidas, J. 2008
  • Probabilistic Fingerprints for Shapes Mitra, Niloy, J., Guibas, L., Giesen, J., Pauly, M. 2008
  • MULTI-PERSON TRACKING FROM SPARSE 3D TRAJECTORIES IN A CAMERA SENSOR NETWORK 2nd ACM/IEEE International Conference on Distributed Smart Cameras Heath, K., Guibas, L. IEEE. 2008: 48–56
  • On incremental rendering of silhouette maps of a polyhedral scene COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS Efrat, A., Guibas, L. J., Hall-Holt, O. A., Zhang, L. 2007; 38 (3): 129-138
  • A package for exact kinetic data structures and sweepline algorithms COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS Russel, D., Karavelas, M. I., Guibas, L. J. 2007; 38 (1-2): 111-127

    Abstract

    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 various considerations, including extensibility, support for multiple kinetic data structures, access to existing data structures and algorithms in CGAL, as well as debugging. Due to the similarity between the operations involved, the software can also be used to compute arrangements of polynomial objects using a sweepline approach. The package consists of three main parts, the kinetic data structure framework support code, an algebraic kernel which implements the set of algebraic operations required for kinetic data structure processing, and kinetic data structures for Delaunay triangulations in one and two dimensions, and Delaunay and regular triangulations in three dimensions. The models provided for the algebraic kernel support both exact operations and inexact approximations with heuristics to improve numerical stability.

    View details for DOI 10.1016/j.comgeo.2006.11.006

    View details for Web of Science ID 000247580500007

    View details for PubMedCentralID PMC3001684

  • Toward unsupervised segmentation of semi-rigid low-resolution molecular surfaces ALGORITHMICA Guibas, L. J., Wang, Y. 2007; 48 (4): 433-448
  • Persistent voids: a new structural metric for membrane fusion BIOINFORMATICS Kasson, P. M., Zornorodian, A., Park, S., Singhal, N., Guibas, L. J., Pande, V. S. 2007; 23 (14): 1753-1759

    Abstract

    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 been unable to resolve early fusion events in fine structural detail. We have previously used molecular dynamics simulations to develop mechanistic models of fusion by small lipid vesicles. Here, we introduce a novel structural measurement of vesicle topology and fusion geometry: persistent voids.Persistent voids calculations enable systematic measurement of structural changes in vesicle fusion by assessing fusion stalk widths. They also constitute a generally applicable technique for assessing lipid topological change. We use persistent voids to compute dynamic relationships between hemifusion neck widening and formation of a full fusion pore in our simulation data. We predict that a tightly coordinated process of hemifusion neck expansion and pore formation is responsible for the rapid vesicle fusion mechanism, while isolated enlargement of the hemifusion diaphragm leads to the formation of a metastable hemifused intermediate. These findings suggest that rapid fusion between small vesicles proceeds via a small hemifusion diaphragm rather than a fully expanded one.Software available upon request pending public release.Supplementary data are available on Bioinformatics online.

    View details for DOI 10.1093/bioinformatics/btm250

    View details for Web of Science ID 000249248300006

    View details for PubMedID 17488753

  • Symmetrization ACM SIGGRAPH 2007 Conference Mitra, N. J., Guibas, L. J., Pauly, M. ASSOC COMPUTING MACHINERY. 2007
  • Adaptively sampled particle fluids ACM SIGGRAPH 2007 Conference Adams, B., Pauly, M., Keiser, R., Guibas, L. J. ASSOC COMPUTING MACHINERY. 2007
  • Learning smooth shapes by probing 21st Annual Symposium on Computational Geometry Boissonnat, J., Guibas, L. J., Oudot, S. ELSEVIER SCIENCE BV. 2007: 38–58
  • Landmark selection and greedy landmark-descent routing for sensor networks 26th IEEE Conference on Computer Communications (INFOCOM 2007) Nguyen, A., Milosavljevic, N., Fang, Q., Gao, J., Guibas, L. J. IEEE. 2007: 661–669
  • Sparse Data Aggregation in Sensor Networks Gao, J., Guibas, L., Hershberger, J., Milosavljevic, N. 2007
  • Reconstruction of Deforming Geometry from Time-Varying Point Clouds. Wand, M., Jenke, P., Huang, Q., Bokeloh, M., Guibas, L., Schilling, A. 2007
  • Dynamic Geometry Registration. Mitra, Niloy, J., Floery, S., Ovsjanikov, M., Gelfand, N., Guibas, L., Pottmann, H. 2007
  • Compressed sensing and time-parallel reduced-order modeling for structural health monitoring using a DDDAS 7th International Conference on Computational Science (ICCS 2007) Cortial, J., Farhat, C., Guibas, L. J., Rajashekhar, M. SPRINGER-VERLAG BERLIN. 2007: 1171–1179
  • FaceNet: Tracking people and acquiring canonical face images in a wireless camera sensor network 1st ACM/IEEE International Conference on Distributed Smart Cameras (ICDSC-07) Heath, K., Guibas, L. IEEE. 2007: 112–119
  • Object tracking in the presence of occlusions via a camera network 6th International Symposium on Information Processing Sensor Networks Ercan, A. O., El Gamal, A., Guibas, L. J. ASSOC COMPUTING MACHINERY. 2007: 509–518
  • Energy efficient intrusion detection in camera sensor networks 3rd IEEE International Conference on Distributed Computing in Sensor Systems Skraba, P., Guibas, L. SPRINGER-VERLAG BERLIN. 2007: 309–323
  • Geometric filtering of pairwise atomic interactions applied to the design of efficient statistical potentials COMPUTER AIDED GEOMETRIC DESIGN Zomorodian, A., Guibas, L., Koehl, P. 2006; 23 (6): 531-544
  • Deformable spanners and applications 20th ACM Symposium on Computational Geometry Gao, J., Guibas, L. J., Nguyen, A. ELSEVIER SCIENCE BV. 2006: 2–19

    Abstract

    For a set S of points in ℝ(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 times the Euclidean distance between the points. In this paper we propose a new sparse (1 + ε)-spanner with O(n/ε(d)) edges, where ε is a specified parameter. The key property of this spanner is that it can be efficiently maintained under dynamic insertion or deletion of points, as well as under continuous motion of the points in both the kinetic data structures setting and in the more realistic blackbox displacement model we introduce. Our deformable spanner succinctly encodes all proximity information in a deforming point cloud, giving us efficient kinetic algorithms for problems such as the closest pair, the near neighbors of all points, approximate nearest neighbor search (aka approximate Voronoi diagram), well-separated pair decompositions, and approximate k-centers.

    View details for DOI 10.1016/j.comgeo.2005.10.001

    View details for Web of Science ID 000238302900002

    View details for PubMedCentralID PMC3001688

  • Partial and approximate symmetry detection for 3D geometry ACM TRANSACTIONS ON GRAPHICS Mitra, N. J., Guibas, L. J., Pauly, M. 2006; 25 (3): 560-568
  • Locating and bypassing holes in sensor networks MOBILE NETWORKS & APPLICATIONS Fang, Q., Gao, J., Guibas, L. J. 2006; 11 (2): 187-200
  • Landmark-based information storage and retrieval in sensor networks IEEE INFOCOM 2006 Conference/25th IEEE International Conference on Computer Communications Fang, Q., Gao, J., Guibas, L. J. IEEE. 2006: 351–361
  • Camera network node selection for target localization in the presence of occlusions Ercan, A., O., Gamal, A., El, Guibas, L., J. 2006
  • The identity management Kalman filter (IMKF) Schumitsch, B., Thrun, S., Guibas, L., Olukotun, K. 2006
  • Towards a dynamic data driven system for structural and material health monitoring 6th International Conference on Computational Science (ICCS 2006) Farhat, C., Michopoulos, J. G., Chang, F. K., Guibas, L. J., Lew, A. J. SPRINGER-VERLAG BERLIN. 2006: 456–464
  • Kinetically stable task assignment for networks of microservers 5th International Conference on Informational Processing in Sensor Networks Abrams, Z., Chen, H., Guibas, L., Liu, J., Zhao, F. ASSOC COMPUTING MACHINERY. 2006: 93–101
  • Towards unsupervised segmentation of semi-rigid low-resolution molecular surfaces 4th International Conference on Geometric Modeling and Processing (GMP 2006) Wang, Y., Guibas, L. J. SPRINGER-VERLAG BERLIN. 2006: 129–142
  • Optimal placement and selection of camera network nodes for target localization 2nd IEEE International Conference on Distributed Computing in Sensor Systems Ercan, A. O., Yang, D. B., El Gamal, A., Guibas, L. J. SPRINGER-VERLAG BERLIN. 2006: 389–404
  • Efficient collision detection among moving spheres with unknown trajectories ALGORITHMICA Kim, H. K., Guibas, L. J., Shin, S. Y. 2005; 43 (3): 195-210
  • Automated crystallographic ligand building using the medial axis transform of an electron-density isosurface ACTA CRYSTALLOGRAPHICA SECTION D-BIOLOGICAL CRYSTALLOGRAPHY Aishima, J., Russel, D. S., Guibas, L. J., Adams, P. D., Brunger, A. T. 2005; 61: 1354-1363

    Abstract

    Automatic fitting methods that build molecules into electron-density maps usually fail below 3.5 A resolution. As a first step towards addressing this problem, an algorithm has been developed using an approximation of the medial axis to simplify an electron-density isosurface. This approximation captures the central axis of the isosurface with a graph which is then matched against a graph of the molecular model. One of the first applications of the medial axis to X-ray crystallography is presented here. When applied to ligand fitting, the method performs at least as well as methods based on selecting peaks in electron-density maps. Generalization of the method to recognition of common features across multiple contour levels could lead to powerful automatic fitting methods that perform well even at low resolution.

    View details for DOI 10.1107/S0907444905023152

    View details for Web of Science ID 000232353500006

    View details for PubMedID 16204887

  • Meshless animation of fracturing solids ACM SIGGRAPH 2005 Conference Pauly, M., Keiser, R., Adams, B., Dutre, P., Gross, M., Guibas, L. J. ASSOC COMPUTING MACHINERY. 2005: 957–64

    Abstract

    We present a new meshless animation framework for elastic and plastic materials that fracture. Central to our method is a highly dynamic surface and volume sampling method that supports arbitrary crack initiation, propagation, and termination, while avoiding many of the stability problems of traditional mesh-based techniques. We explicitly model advancing crack fronts and associated fracture surfaces embedded in the simulation volume. When cutting through the material, crack fronts directly affect the coupling between simulation nodes, requiring a dynamic adaptation of the nodal shape functions. We show how local visibility tests and dynamic caching lead to an efficient implementation of these effects based on point collocation. Complex fracture patterns of interacting and branching cracks are handled using a small set of topological operations for splitting, merging, and terminating crack fronts. This allows continuous propagation of cracks with highly detailed fracture surfaces, independent of the spatial resolution of the simulation nodes, and provides effective mechanisms for controlling fracture paths. We demonstrate our method for a wide range of materials, from stiff elastic to highly plastic objects that exhibit brittle and/or ductile fracture.

    View details for Web of Science ID 000231223700076

    View details for PubMedCentralID PMC3001686

  • Inverse kinematics in biology: The protein loop closure problem INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH Kolodny, R., Guibas, L., Levitt, M., Koehl, P. 2005; 24 (2-3): 151-163
  • Exploring protein folding trajectories using geometric spanners 10th Annual Pacific Symposium on Biocomputing (PSB) Russel, D., Guibas, L. WORLD SCIENTIFIC PUBL CO PTE LTD. 2005: 40–51

    Abstract

    We describe the 3-D structure of a protein using geometric spanners--geometric graphs with a sparse set of edges where paths approximate the n2 inter-atom distances. The edges in the spanner pick out important proximities in the structure, labeling a small number of atom pairs or backbone region pairs as being of primary interest. Such compact multiresolution views of proximities in the protein can be quite valuable, allowing, for example, easy visualization of the conformation over the entire folding trajectory of a protein and segmentation of the trajectory. These visualizations allow one to easily detect formation of secondary and tertiary structures as the protein folds.

    View details for Web of Science ID 000230169100004

    View details for PubMedID 15759612

  • Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points Agarwal, P., K., Berg, M., De, Gao, J., Guibas, Leonidas, J., Har-Peled, S. 2005
  • Example-Based 3D Scan Completion. Pauly, M., Mitra, N., J., Giesen, J., Gross, M., Guibas, L. 2005
  • Persistence Barcodes for Shapes. International Journal of Shape Modeling Carlsson, G., Zomorodian, A., Collins, A., Guibas, L. 2005; 11: 149-187
  • GLIDER: Gradient Landmark-Based Distributed Routing for sensor networks 24th Annual Joint Conference of the IEEE Computer and Communications Societies Fang, Q., Gao, J., Guibas, L. J., de Silva, V., Zhang, L. IEEE COMPUTER SOC. 2005: 339–350
  • Efficient raytracing of deforming point-sampled surfaces 26th Annual Conference of the Eurographics-Association Adams, B., Keiser, R., Pauly, M., Guibas, L. J., Gross, M., Dutre, P. WILEY-BLACKWELL. 2005: 677–84
  • Lazy inference on object identities in wireless sensor networks 4th International Symposium on Information Processing in Sensor Networks Shin, J., Lee, N., Thrun, S., Guibas, L. IEEE. 2005: 174–180
  • Distributed proximity maintenance in ad hoc mobile networks 1st IEEE International Conference on Distributed Computing in Sensor Systems Gao, J., Guibas, L. J., Nguyen, A. SPRINGER-VERLAG BERLIN. 2005: 4–19
  • Geometric spanners for routing in mobile networks IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS Gao, J., Guibas, L. J., Hershberger, J., Zhang, L., Zhu, A. 2005; 23 (1): 174-185
  • A barcode shape descriptor for curve point cloud data COMPUTERS & GRAPHICS-UK Collins, A., Zomorodian, A., Carlsson, G., Guibas, L. J. 2004; 28 (6): 881-894
  • Apply geometric duality to energy-efficient non-local phenomenon awareness using sensor networks IEEE WIRELESS COMMUNICATIONS Liu, J., Zhao, F., Cheung, P., Guibas, L. 2004; 11 (6): 62-68
  • Estimating surface normals in noisy point cloud data 19th ACM Symposium on Computational Geometry Mitra, N. J., Nguyen, A., Guibas, L. WORLD SCIENTIFIC PUBL CO PTE LTD. 2004: 261–76
  • Collision detection for deforming necklaces 18th Annual Symposium on Computational Geometry Agarwal, P., Guibas, L., Nguyen, A., Russel, D., Zhang, L. ELSEVIER SCIENCE BV. 2004: 137–63
  • Fractionally cascaded information in a sensor network 3rd International Symposium on Information Processing in Sensor Networks Gao, J., Guibas, L. J., Hershberger, J., Zhang, L. ASSOC COMPUTING MACHINERY. 2004: 311–319
  • Kinetic Data Structures. Handbook of Data Structures and Applications Guibas, L. edited by Mehta, D., Sahni, S. Chapman and Hall/CRC. 2004: 1
  • Modeling Motion. Handbook of Discrete and Computational Geometry Guibas, L. edited by Goodman, J., O'Rourke, J. Chapman and Hall/CRC. 2004; 2nd: 1117–1134
  • Persistence Barcodes for Shapes. Carlsson, G., Zomorodian, A., Collins, A., Guibas, L. 2004
  • Sensor Tasking for Occupancy Reasoning in a Camera Network IEEE/ICST 1st Workshop on Broadband Advanced Sensor Networks (BASENETS 2004). Yang, D., Shin, J., Ercan, A., Guibas, L. 2004
  • Uncertainty and Variability in Point Cloud Surface Data. Pauly, M., Mitra, N., J., Guibas, L. 2004
  • Registration of Point Cloud Data from a Geometric Optimization Perspective. Mitra, N., J., Gelfand, N., Pottmann, H., Guibas, L. 2004
  • An Empirical Comparison of Techniques for Updating Delaunay Triangulations Guibas, L., Russel, D. 2004
  • Wireless Sensor Networks: An Information Processing Approach. Zhao, F., Guibas, L. Elsevier/Morgan-Kaufmann. 2004
  • A Computational Framework for Handling Motion. ALENEX Guibas, L., Karavelas, M., Russel, D. 2004: 129-141
  • Quasi-Rigid Objects in Contact Pauly, M., Pai, D., K., Guibas, L., J. 2004
  • Shape Segmentation Using Local Slippage Analysis. Gelfand, N., Guibas, L. 2004
  • Robust Global Registration. Gelfand, N., Mitra, N., Guibas, L., Pottmann, H. 2004
  • RoamHBA: Maintaining group connectivity in sensor networks 3rd International Symposium on Information Processing in Sensor Networks Fang, Q., Liu, J., Guibas, L., Zhao, F. ASSOC COMPUTING MACHINERY. 2004: 151–160
  • Locating and bypassing routing holes in sensor networks 23rd Annual Joint Conference of the IEEE Computer and Communications Societies Fang, Q., Gao, H., Guibas, L. J. IEEE. 2004: 2458–2468
  • A probabilistic approach to inference with limited information in sensor networks 3rd International Symposium on Information Processing in Sensor Networks Biswas, R., Thrun, S., Guibas, L. J. ASSOC COMPUTING MACHINERY. 2004: 269–276
  • Collaborative signal and information processing: An information-directed approach PROCEEDINGS OF THE IEEE Zhao, F., Liu, J., Liu, J., Guibas, L., Reich, J. 2003; 91 (8): 1199-1209
  • Discrete mobile Centers 17th Annual Symposium on Computational Geometry Gao, J., Guibas, L. J., Hershberger, J., Zhang, L., Zhu, A. SPRINGER. 2003: 45–63
  • Zonotopes as bounding volumes 14th Annual ACM-SIAM Symposium on Discrete Algorithms Guibas, L. J., Nguyen, A., Zhang, L. SIAM. 2003: 803–812
  • Distributed Algorithm for Managing Multi-Target Identities in Wireless Ad-hoc Sensor Networks. 2nd Int'l Workshop on Information Processing in Sensor Networks (IPSN) 2003 Shin, J., Guibas, L., Zhao, F. 2003: 223-238
  • Lightweight Sensing and Communication Protocols for Target Enumeration and Aggregation Fang, Q., Zhao, F., Guibas, L. 2003
  • Multiple-target tracking and identity management 2nd IEEE International Conference on Sensors Hwang, I., Balakrishnan, H., Roy, K., Shin, J., Guibas, L., Tomlin, C. IEEE. 2003: 36–41
  • Counting people in crowds with a real-time network of simple image sensors 9th IEEE International Conference on Computer Vision Yang, D. B., Gonzalez-Banos, H. H., Guibas, L. J. IEEE COMPUTER SOC. 2003: 122–129
  • Small libraries of protein fragments model native protein structures accurately JOURNAL OF MOLECULAR BIOLOGY Kolodny, R., Koehl, P., Guibas, L., Levitt, M. 2002; 323 (2): 297-307

    Abstract

    Prediction of protein structure depends on the accuracy and complexity of the models used. Here, we represent the polypeptide chain by a sequence of rigid fragments that are concatenated without any degrees of freedom. Fragments chosen from a library of representative fragments are fit to the native structure using a greedy build-up method. This gives a one-dimensional representation of native protein three-dimensional structure whose quality depends on the nature of the library. We use a novel clustering method to construct libraries that differ in the fragment length (four to seven residues) and number of representative fragments they contain (25-300). Each library is characterized by the quality of fit (accuracy) and the number of allowed states per residue (complexity). We find that the accuracy depends on the complexity and varies from 2.9A for a 2.7-state model on the basis of fragments of length 7-0.76A for a 15-state model on the basis of fragments of length 5. Our goal is to find representations that are both accurate and economical (low complexity). The models defined here are substantially better in this regard: with ten states per residue we approximate native protein structure to 1A compared to over 20 states per residue needed previously. For the same complexity, we find that longer fragments provide better fits. Unfortunately, libraries of longer fragments must be much larger (for ten states per residue, a seven-residue library is 100 times larger than a five-residue library). As the number of known protein native structures increases, it will be possible to construct larger libraries to better exploit this correlation between neighboring residues. Our fragment libraries, which offer a wide range of optimal fragments suited to different accuracies of fit, may prove to be useful for generating better decoy sets for ab initio protein folding and for generating accurate loop conformations in homology modeling.

    View details for DOI 10.1016/S0022-2836(02)00942-7

    View details for Web of Science ID 000178976500011

    View details for PubMedID 12381322

  • Sensing, tracking, and reasoning with relations IEEE SIGNAL PROCESSING MAGAZINE Guibas, L. J. 2002; 19 (2): 73-85
  • Approximate Map Matching with respect to the Fréchet Distance Chen, D., Driemel, A., Guibas, L., Nguyen, A., Wenk, C.
  • Fine-Grained Semi-Supervised Labeling of Large Shape Collections ACM Transactions on Graphics (SIGGRAPH Asia 2013) Huang, Q., Su, H., Guibas, L. ; 6 (32)