Leonidas Guibas
Paul Pigott Professor of Engineering and Professor, by courtesy, of Electrical Engineering
Computer Science
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.
Academic Appointments
-
Professor, Computer Science
-
Professor (By courtesy), Electrical Engineering
-
Member, Bio-X
-
Faculty Affiliate, Institute for Human-Centered Artificial Intelligence (HAI)
-
Affiliate, Stanford Woods Institute for the Environment
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)
-
Member, National Academy of Sciences (2022)
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.
2024-25 Courses
- Geometric and Topological Data Analysis
CME 251 (Spr) - Topics in Geometric Computing - 3D and 4D Foundation Models
CS 468 (Aut) -
Independent Studies (18)
- Advanced Reading and Research
CS 499 (Aut, Win, Spr) - Advanced Reading and Research
CS 499P (Aut, Win, Spr) - Biomedical Informatics Teaching Methods
BIOMEDIN 290 (Aut, Win, Spr, Sum) - Curricular Practical Training
CS 390A (Aut, Win, Spr) - Curricular Practical Training
CS 390B (Aut, Win, Spr) - Curricular Practical Training
CS 390C (Aut, Win, Spr) - Directed Reading and Research
BIOMEDIN 299 (Aut, Win, Spr, Sum) - Independent Project
CS 399 (Aut, Win, Spr) - Independent Project
CS 399P (Aut, Win, Spr) - Independent Work
CS 199 (Aut, Win, Spr) - Independent Work
CS 199P (Aut, Win, Spr) - Medical Scholars Research
BIOMEDIN 370 (Aut, Win, Spr, Sum) - Part-time Curricular Practical Training
CS 390D (Aut, Win, Spr) - Ph.D. Research
CME 400 (Aut, Win, Spr) - Programming Service Project
CS 192 (Aut, Win, Spr) - Senior Project
CS 191 (Aut, Win, Spr) - Supervised Undergraduate Research
CS 195 (Aut, Win, Spr) - Writing Intensive Senior Research Project
CS 191W (Aut, Win, Spr)
- Advanced Reading and Research
-
Prior Year Courses
2023-24 Courses
- Geometric and Topological Data Analysis
CME 251, CS 233 (Win)
2022-23 Courses
- Neural Models for 3D Geometry
CS 348N (Spr)
2021-22 Courses
- Geometric and Topological Data Analysis
CME 251, CS 233 (Spr) - Neural Models for 3D Geometry
CS 348N (Win)
- Geometric and Topological Data Analysis
Stanford Advisees
-
Postdoctoral Faculty Sponsor
Francis Engelmann, Adam Harley, Guandao Yang, Yang You -
Doctoral Dissertation Advisor (AC)
Connor Lin, Colton Stearns -
Orals Evaluator
Connor Lin -
Doctoral Dissertation Co-Advisor (AC)
Shengqu Cai, Boyang Deng -
Master's Program Advisor
Govind Chada, Jimmy Chen, Wayne Chinganga, Manh Dao, Karthik Jetty, Christian Jonas, Shubh Khanna, Shiva Khanna Yamamoto, Cole Lee, Maddie Reynolds, Samantha Silverstein, Bar Weiner, Shumann Xu, Zhenyu Zhang, Michael Zhu -
Doctoral (Program)
Hansheng Chen, Congyue Deng, Ian Huang, Jihyeon Je, Connor Lin, Boxiao Pan, Colton Stearns, Yijia Weng, Yang Zheng
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
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)
2020: 1566–76
View details for DOI 10.1109/CVPR42600.2020.00164
-
Learning Multiview 3D Point Cloud Registration
IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
2020: 1756–66
View details for DOI 10.1109/CVPR42600.2020.00183
-
Dirichlet Energy for Analysis and Synthesis of Soft Maps
COMPUTER GRAPHICS FORUM
2013; 32 (5): 197-206
View details for DOI 10.1111/cgf.12186
View details for Web of Science ID 000323204000020
-
Consistent Shape Maps via Semidefinite Programming
COMPUTER GRAPHICS FORUM
2013; 32 (5): 177-186
View details for DOI 10.1111/cgf.12184
View details for Web of Science ID 000323204000018
-
Shape Matching via Quotient Spaces
COMPUTER GRAPHICS FORUM
2013; 32 (5): 1-11
View details for DOI 10.1111/cgf.12167
View details for Web of Science ID 000323204000001
-
Map-Based Exploration of Intrinsic Shape Differences and Variability
ACM TRANSACTIONS ON GRAPHICS
2013; 32 (4)
View details for DOI 10.1145/2461912.2461959
View details for Web of Science ID 000321840100041
-
Building Markov state models with solvent dynamics
11th Asia Pacific Bioinformatics Conference (APBC)
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 2013
- Locating Lucrative Passengers for Taxicab Drivers. 2013
- Large-Scale Joint Map Matching of GPS Traces 2013
- Image Co-Segmentation via Consistent Functional Maps. 2013
- Wavelets on Graphs via Deep Learning NIPS 2013
- Pathlet Learning for Compressing and Planning Trajectories. 2013
- Guided Real-Time Scanning of Indoor Environments, Computer Graphics Forum 2013
- Guided Real-Time Scanning of Indoor Environments Computer Graphics Forum, Pacific Graphics 2013
-
Acquiring 3D Indoor Environments with Variability and Repetition
ACM TRANSACTIONS ON GRAPHICS
2012; 31 (6)
View details for DOI 10.1145/2366145.2366157
View details for Web of Science ID 000311298900012
-
Microtiles: Extracting Building Blocks from Correspondences
COMPUTER GRAPHICS FORUM
2012; 31 (5): 1597-1606
View details for DOI 10.1111/j.1467-8659.2012.03165.x
View details for Web of Science ID 000307307500004
-
Functional Maps: A Flexible Representation of Maps Between Shapes
ACM TRANSACTIONS ON GRAPHICS
2012; 31 (4)
View details for DOI 10.1145/2185520.2185526
View details for Web of Science ID 000308250300006
- Detecting Network Cliques with Radon Basis Pursuit. 2012
- Supervised Earth Mover's Distance Learning and its Computer Vision Applications 2012
-
Joint Shape Segmentation with Linear Programming
ACM TRANSACTIONS ON GRAPHICS
2011; 30 (6)
View details for DOI 10.1145/2024156.2024159
View details for Web of Science ID 000297681100003
-
A Condition Number for Non-Rigid Shape Matching
COMPUTER GRAPHICS FORUM
2011; 30 (5): 1503-1512
View details for DOI 10.1111/j.1467-8659.2011.02024.x
View details for Web of Science ID 000293524100014
-
An Optimization Approach to Improving Collections of Shape Maps
COMPUTER GRAPHICS FORUM
2011; 30 (5): 1481-1491
View details for DOI 10.1111/j.1467-8659.2011.02022.x
View details for Web of Science ID 000293524100012
-
As-Killing-As-Possible Vector Fields for Planar Deformation
COMPUTER GRAPHICS FORUM
2011; 30 (5): 1543-1552
View details for DOI 10.1111/j.1467-8659.2011.02028.x
View details for Web of Science ID 000293524100018
-
Probabilistic Reasoning for Assembly-Based 3D Modeling
ACM TRANSACTIONS ON GRAPHICS
2011; 30 (4)
View details for DOI 10.1145/1964921.1964930
View details for Web of Science ID 000297216400009
-
Exploration of Continuous Variability in Collections of 3D Shapes
ACM TRANSACTIONS ON GRAPHICS
2011; 30 (4)
View details for DOI 10.1145/1964921.1964928
View details for Web of Science ID 000297216400007
-
Discovery of Intrinsic Primitives on Triangle Meshes
COMPUTER GRAPHICS FORUM
2011; 30 (2): 365-374
View details for DOI 10.1111/j.1467-8659.2011.01867.x
View details for Web of Science ID 000289996100014
- Overcomplete Radon Bases for Target Property Management in Sensor Networks. 2011
- Data- driven trajectory smoothing. 2011
- A Fourier-Theoretic Approach for Inferring Symmetries. 2011
- Persistence-based clustering in riemannian manifolds. 2011
- Kinetically-aware Conformational Distances in Molecular Dynamics. 2011
-
Metric Graph Reconstruction from Noisy Data
27th Annual ACM Symposium on Computational Geometry
ASSOC COMPUTING MACHINERY. 2011: 37–46
View details for Web of Science ID 000292906900005
-
Fourier-Information Duality in the Identity Management Problem
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)
SPRINGER-VERLAG BERLIN. 2011: 97–113
View details for Web of Science ID 000316551300007
-
Network Warehouses: Efficient Information Distribution to Mobile Users
IEEE INFOCOM Conference
IEEE. 2011: 2069–2077
View details for Web of Science ID 000297374702036
-
Human Action Recognition by Learning Bases of Action Attributes and Parts
IEEE International Conference on Computer Vision (ICCV)
IEEE. 2011: 1331–1338
View details for Web of Science ID 000300061900169
-
Witnessed k-Distance
27th Annual ACM Symposium on Computational Geometry
ASSOC COMPUTING MACHINERY. 2011: 57–64
View details for Web of Science ID 000292906900007
-
Geodesic Patterns
ACM TRANSACTIONS ON GRAPHICS
2010; 29 (4)
View details for DOI 10.1145/1778765.1778780
View details for Web of Science ID 000279806600015
-
One Point Isometric Matching with the Heat Kernel
COMPUTER GRAPHICS FORUM
2010; 29 (5): 1555-1564
View details for DOI 10.1111/j.1467-8659.2010.01764.x
View details for Web of Science ID 000282019900006
-
On Discrete Killing Vector Fields and Patterns on Surfaces
COMPUTER GRAPHICS FORUM
2010; 29 (5): 1701-1711
View details for DOI 10.1111/j.1467-8659.2010.01779.x
View details for Web of Science ID 000282019900021
-
Image Webs: Computing and Exploiting Connectivity in Image Collections
23rd IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
IEEE COMPUTER SOC. 2010: 3432–3439
View details for Web of Science ID 000287417503062
- Data Stashing: Energy-Efficient Information Delivery to Mobile Sinks through Trajectory Prediction. 2010
- Persistence-based Segmentation of Deformable Shapes, 3rd Workshop on Non-Rigid Shape Analysis and Deformable Image Alignment 2010
- Kinetic Stable Delaunay Graphs. 2010
- Constructing Multi-Resolution Markov State Models (MSMs)to Elucidate RNA Hairpin Folding Mechanisms. 2010
-
Meshless Shape and Motion Design for Multiple Deformable Objects
COMPUTER GRAPHICS FORUM
2010; 29 (1): 43-59
View details for DOI 10.1111/j.1467-8659.2009.01536.x
View details for Web of Science ID 000274388400005
-
Road Network Reconstruction for Organizing Paths
21st Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2010: 1309–1320
View details for Web of Science ID 000280699900105
-
Robust Single-View Geometry and Motion Reconstruction
ACM SIGGRAPH Asia Conference 2009
ASSOC COMPUTING MACHINERY. 2009
View details for DOI 10.1145/1618452.1618521
View details for Web of Science ID 000273315300070
-
Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes
23rd Annual Symposium on Computational Geometry
SPRINGER. 2009: 37–70
View details for DOI 10.1007/s00454-009-9175-1
View details for Web of Science ID 000266240300004
-
A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion
7th Eurographics Symposium on Geometry Processing (SGP)
WILEY-BLACKWELL. 2009: 1383–92
View details for Web of Science ID 000268597500014
-
Gromov-Hausdorff Stable Signatures for Shapes using Persistence
7th Eurographics Symposium on Geometry Processing (SGP)
WILEY-BLACKWELL. 2009: 1393–1403
View details for Web of Science ID 000268597500015
-
Topological methods for exploring low-density states in biomolecular folding pathways
JOURNAL OF CHEMICAL PHYSICS
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
2009; 28 (2)
View details for DOI 10.1145/1516522.1516526
View details for Web of Science ID 000266818600004
-
Interference-Aware MAC Protocol for Wireless Networks by a Game-Theoretic Approach
IEEE INFOCOM Conference 2009
IEEE. 2009: 1854–1862
View details for Web of Science ID 000275366201006
- Proximity of Persistence Modules and their Diagrams. 2009
- ShapeGoogle: a computer vision approach for invariant shape retrieval 2009
- Robust Voronoi-based Curvature and Feature Estimation 2009
- Dynamic Resource Management and Matching in Sensor Networks 2009
- Analysis of Scalar Fields over Point Cloud Data. 2009
-
Lightweight Coloring and Desynchronization for Networks
IEEE INFOCOM Conference 2009
IEEE. 2009: 2383–2391
View details for Web of Science ID 000275366201065
-
Shape Decomposition using Modal Analysis
COMPUTER GRAPHICS FORUM
2009; 28 (2): 407-416
View details for DOI 10.1111/j.1467-8659.2009.01380.x
View details for Web of Science ID 000264544700026
-
Predictive QoS Routing to Mobile Sinks in Wireless Sensor Networks
8th International Symposium on Information Processing Sensor Networks
IEEE. 2009: 109–120
View details for Web of Science ID 000275711800010
-
Reconstruction using witness complexes
DISCRETE & COMPUTATIONAL GEOMETRY
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
ASSOC COMPUTING MACHINERY. 2008
View details for DOI 10.1145/1360612.1360642
View details for Web of Science ID 000258262000032
-
Structural insight into RNA hairpin folding intermediates
JOURNAL OF THE AMERICAN CHEMICAL SOCIETY
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)
WILEY-BLACKWELL. 2008: 1341–48
View details for Web of Science ID 000258223700003
-
Non-rigid registration under isometric deformations
6th Eurographics Symposium on Geometry Processing (SGP 2008)
WILEY-BLACKWELL. 2008: 1449–57
View details for Web of Science ID 000258223700015
-
MULTI-PERSON TRACKING FROM SPARSE 3D TRAJECTORIES IN A CAMERA SENSOR NETWORK
2nd ACM/IEEE International Conference on Distributed Smart Cameras
IEEE. 2008: 48–56
View details for Web of Science ID 000263466700006
- Localization of Mobile Users Using Trajectory Matching. 2008
- Enabling data interpretation through user collaboration in sensor networks 2008
- Bounded uncertainty roadmaps for path planning. 2008
- Geodesic Delaunay Triangulation and Witness Complex in the Plane. 2008
- The Identity Management Problem — A Short Survey. 2008
- Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks 2008
- Composable Information Gradients in Wireless Sensor Networks 2008
- Probabilistic Fingerprints for Shapes 2008
-
Robust Extraction of 1D Skeletons from Grayscale 3D Images
19th International Conference on Pattern Recognition (ICPR 2008)
IEEE. 2008: 2112–2115
View details for Web of Science ID 000264729001035
-
On incremental rendering of silhouette maps of a polyhedral scene
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
2007; 38 (3): 129-138
View details for DOI 10.1016/j.comgeo.2006.12.003
View details for Web of Science ID 000249488900001
-
A package for exact kinetic data structures and sweepline algorithms
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
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
2007; 48 (4): 433-448
View details for DOI 10.1007/s00453-007-0151-y
View details for Web of Science ID 000248325000009
-
Persistent voids: a new structural metric for membrane fusion
BIOINFORMATICS
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
ASSOC COMPUTING MACHINERY. 2007
View details for DOI 10.1145/1239451.1239514
View details for Web of Science ID 000248914000066
-
Adaptively sampled particle fluids
ACM SIGGRAPH 2007 Conference
ASSOC COMPUTING MACHINERY. 2007
View details for DOI 10.1145/1239451.1239499
View details for Web of Science ID 000248914000051
-
Learning smooth shapes by probing
21st Annual Symposium on Computational Geometry
ELSEVIER SCIENCE BV. 2007: 38–58
View details for DOI 10.1016/j.comgeo.2006.05.008
View details for Web of Science ID 000245339400005
-
Landmark selection and greedy landmark-descent routing for sensor networks
26th IEEE Conference on Computer Communications (INFOCOM 2007)
IEEE. 2007: 661–669
View details for Web of Science ID 000249117701016
- Sparse Data Aggregation in Sensor Networks 2007
- Reconstruction of Deforming Geometry from Time-Varying Point Clouds. 2007
- Dynamic Geometry Registration. 2007
-
Compressed sensing and time-parallel reduced-order modeling for structural health monitoring using a DDDAS
7th International Conference on Computational Science (ICCS 2007)
SPRINGER-VERLAG BERLIN. 2007: 1171–1179
View details for Web of Science ID 000247062800153
-
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)
IEEE. 2007: 112–119
View details for Web of Science ID 000254383500016
-
Object tracking in the presence of occlusions via a camera network
6th International Symposium on Information Processing Sensor Networks
ASSOC COMPUTING MACHINERY. 2007: 509–518
View details for Web of Science ID 000251798600053
-
Energy efficient intrusion detection in camera sensor networks
3rd IEEE International Conference on Distributed Computing in Sensor Systems
SPRINGER-VERLAG BERLIN. 2007: 309–323
View details for Web of Science ID 000247855100021
-
Geometric filtering of pairwise atomic interactions applied to the design of efficient statistical potentials
COMPUTER AIDED GEOMETRIC DESIGN
2006; 23 (6): 531-544
View details for DOI 10.1016/j.cagd.2006.03.002
View details for Web of Science ID 000239260900005
-
Deformable spanners and applications
20th ACM Symposium on Computational Geometry
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
2006; 25 (3): 560-568
View details for Web of Science ID 000239817400012
-
Locating and bypassing holes in sensor networks
MOBILE NETWORKS & APPLICATIONS
2006; 11 (2): 187-200
View details for DOI 10.1007/s11036-006-4471-y
View details for Web of Science ID 000237835400007
-
Landmark-based information storage and retrieval in sensor networks
IEEE INFOCOM 2006 Conference/25th IEEE International Conference on Computer Communications
IEEE. 2006: 351–361
View details for Web of Science ID 000259418000030
- Camera network node selection for target localization in the presence of occlusions 2006
- The identity management Kalman filter (IMKF) 2006
-
Towards unsupervised segmentation of semi-rigid low-resolution molecular surfaces
4th International Conference on Geometric Modeling and Processing (GMP 2006)
SPRINGER-VERLAG BERLIN. 2006: 129–142
View details for Web of Science ID 000239567900010
-
Optimal placement and selection of camera network nodes for target localization
2nd IEEE International Conference on Distributed Computing in Sensor Systems
SPRINGER-VERLAG BERLIN. 2006: 389–404
View details for Web of Science ID 000239426200024
-
Towards a dynamic data driven system for structural and material health monitoring
6th International Conference on Computational Science (ICCS 2006)
SPRINGER-VERLAG BERLIN. 2006: 456–464
View details for Web of Science ID 000238417300061
-
Kinetically stable task assignment for networks of microservers
5th International Conference on Informational Processing in Sensor Networks
ASSOC COMPUTING MACHINERY. 2006: 93–101
View details for Web of Science ID 000238978000013
-
Efficient collision detection among moving spheres with unknown trajectories
ALGORITHMICA
2005; 43 (3): 195-210
View details for DOI 10.1007/s00453-005-1153-2
View details for Web of Science ID 000232830600003
-
Automated crystallographic ligand building using the medial axis transform of an electron-density isosurface
ACTA CRYSTALLOGRAPHICA SECTION D-BIOLOGICAL CRYSTALLOGRAPHY
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
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
2005; 24 (2-3): 151-163
View details for DOI 10.1177/0278364905050352
View details for Web of Science ID 000227409900004
-
Exploring protein folding trajectories using geometric spanners
10th Annual Pacific Symposium on Biocomputing (PSB)
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 2005
- Example-Based 3D Scan Completion. 2005
- Persistence Barcodes for Shapes. International Journal of Shape Modeling 2005; 11: 149-187
-
GLIDER: Gradient Landmark-Based Distributed Routing for sensor networks
24th Annual Joint Conference of the IEEE Computer and Communications Societies
IEEE COMPUTER SOC. 2005: 339–350
View details for Web of Science ID 000231441000031
-
Efficient raytracing of deforming point-sampled surfaces
26th Annual Conference of the Eurographics-Association
WILEY-BLACKWELL. 2005: 677–84
View details for Web of Science ID 000231323800048
-
Geometric spanners for routing in mobile networks
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS
2005; 23 (1): 174-185
View details for DOI 10.1109/JSAC.2004.837364
View details for Web of Science ID 000226063100016
-
Lazy inference on object identities in wireless sensor networks
4th International Symposium on Information Processing in Sensor Networks
IEEE. 2005: 174–180
View details for Web of Science ID 000230452800023
-
Distributed proximity maintenance in ad hoc mobile networks
1st IEEE International Conference on Distributed Computing in Sensor Systems
SPRINGER-VERLAG BERLIN. 2005: 4–19
View details for Web of Science ID 000230375000004
-
A barcode shape descriptor for curve point cloud data
COMPUTERS & GRAPHICS-UK
2004; 28 (6): 881-894
View details for DOI 10.1016/j.cag.2004.08.015
View details for Web of Science ID 000225055200008
-
Apply geometric duality to energy-efficient non-local phenomenon awareness using sensor networks
IEEE WIRELESS COMMUNICATIONS
2004; 11 (6): 62-68
View details for Web of Science ID 000225807500008
-
Estimating surface normals in noisy point cloud data
19th ACM Symposium on Computational Geometry
WORLD SCIENTIFIC PUBL CO PTE LTD. 2004: 261–76
View details for Web of Science ID 000224315900003
-
Collision detection for deforming necklaces
18th Annual Symposium on Computational Geometry
ELSEVIER SCIENCE BV. 2004: 137–63
View details for DOI 10.1016/j.comgeo.2004.03.008
View details for Web of Science ID 000221974900005
-
Fractionally cascaded information in a sensor network
3rd International Symposium on Information Processing in Sensor Networks
ASSOC COMPUTING MACHINERY. 2004: 311–319
View details for Web of Science ID 000222055900036
- Kinetic Data Structures. Handbook of Data Structures and Applications edited by Mehta, D., Sahni, S. Chapman and Hall/CRC. 2004: 1
- Persistence Barcodes for Shapes. 2004
- Sensor Tasking for Occupancy Reasoning in a Camera Network IEEE/ICST 1st Workshop on Broadband Advanced Sensor Networks (BASENETS 2004). 2004
- Uncertainty and Variability in Point Cloud Surface Data. 2004
- Registration of Point Cloud Data from a Geometric Optimization Perspective. 2004
- An Empirical Comparison of Techniques for Updating Delaunay Triangulations 2004
- Wireless Sensor Networks: An Information Processing Approach. Elsevier/Morgan-Kaufmann. 2004
- Quasi-Rigid Objects in Contact 2004
- Shape Segmentation Using Local Slippage Analysis. 2004
- Robust Global Registration. 2004
-
Locating and bypassing routing holes in sensor networks
23rd Annual Joint Conference of the IEEE Computer and Communications Societies
IEEE. 2004: 2458–2468
View details for Web of Science ID 000223848100226
-
A probabilistic approach to inference with limited information in sensor networks
3rd International Symposium on Information Processing in Sensor Networks
ASSOC COMPUTING MACHINERY. 2004: 269–276
View details for Web of Science ID 000222055900031
- Modeling Motion. Handbook of Discrete and Computational Geometry edited by Goodman, J., O'Rourke, J. Chapman and Hall/CRC. 2004; 2nd: 1117–1134
- A Computational Framework for Handling Motion. ALENEX 2004: 129-141
-
RoamHBA: Maintaining group connectivity in sensor networks
3rd International Symposium on Information Processing in Sensor Networks
ASSOC COMPUTING MACHINERY. 2004: 151–160
View details for Web of Science ID 000222055900018
-
Collaborative signal and information processing: An information-directed approach
PROCEEDINGS OF THE IEEE
2003; 91 (8): 1199-1209
View details for DOI 10.1109/JPROC.2003.814921
View details for Web of Science ID 000184655000006
-
Discrete mobile Centers
17th Annual Symposium on Computational Geometry
SPRINGER. 2003: 45–63
View details for DOI 10.1007/s00454-003-2925-6
View details for Web of Science ID 000183405700005
-
Zonotopes as bounding volumes
14th Annual ACM-SIAM Symposium on Discrete Algorithms
SIAM. 2003: 803–812
View details for Web of Science ID 000180994200102
- 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 2003: 223-238
- Lightweight Sensing and Communication Protocols for Target Enumeration and Aggregation 2003
-
Counting people in crowds with a real-time network of simple image sensors
9th IEEE International Conference on Computer Vision
IEEE COMPUTER SOC. 2003: 122–129
View details for Web of Science ID 000186833000017
-
Multiple-target tracking and identity management
2nd IEEE International Conference on Sensors
IEEE. 2003: 36–41
View details for Web of Science ID 000189435400008
-
Small libraries of protein fragments model native protein structures accurately
JOURNAL OF MOLECULAR BIOLOGY
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
2002; 19 (2): 73-85
View details for Web of Science ID 000173993100008
- Approximate Map Matching with respect to the Fréchet Distance
- Fine-Grained Semi-Supervised Labeling of Large Shape Collections ACM Transactions on Graphics (SIGGRAPH Asia 2013) ; 6 (32)