Published on January 29, 2009
Consistent approximation of geodesics in graphs Tutorial 3 © Alexander & Michael Bronstein tosca.cs.technion.ac.il/book Numerical geometry of non-rigid shapes Stanford University, Winter 2009
Troubles with the metric Inconsistent Consistent Geodesic approximation consistency depends on the graph
Consistent metric approximation Find a bound of the form Sampling quality Graph connectivity Surface properties where , depend on
Main idea Sampling Connectivity graph Geodesic metric Length metric Sampled metric Main idea: show
Sampling conditions Proposition 1 (Bernstein et al. 2000) Let and . Suppose -neighborhood connectivity is a -covering Then
is a -covering
Sketch of the proof is straightforward Let be the geodesic between and of length Divide the geodesic into segments of length at points Due to sampling density, there exist at most -distant from By triangle inequality hence The length of the path
Surface properties Minimum curvature radius Minimum branch separation :
Surface properties Proposition 2 (Bernstein et al. 2000) Let . Suppose Then
Sufficient conditions for consistency Theorem (Bernstein et al. 2000) Let , and . Suppose Connectivity is a -covering The length of edges is bounded Then
is a -covering
The length of edges is bounded
Proof Since , condition implies Then, we have: (straightforward) (Proposition 1)
Proof (cont) Let be the shortest graph path between and Condition allows to apply Proposition 2 for each of the path segments which gives
Why both conditions are important? Insufficient density Too long edges
Probabilistic version Suppose the sampling is chosen randomly with density function Given , for sufficiently large holds with probability at least
Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...
In this presentation we will describe our experience developing with a highly dyna...
Presentation to the LITA Forum 7th November 2014 Albuquerque, NM
Un recorrido por los cambios que nos generará el wearabletech en el futuro
Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...
3 Numerical geometry of non-rigid shapes Consistent approximation of geodesics in graphs Consistent metric approximation ... graphs Consistent ...
Consistent approximation of geodesics in graphs ... Numerical geometry of non-rigid shapes ... of geodesics in graphs 3 Consistent metric approximation
1 Numerical geometry of non-rigid shapes Shortest path problems Shortest path problems Lecture 2 © Alexander & Michael Bronstein tosca.cs.technion.ac.il ...
Numerical geometry of non-rigid shapes Stanford ... the graph Consistent metric approximation Find a ... in graphs * * * * Numerical geometry of non ...
... and begins his treatment by introducing such modern concepts as a metric ... KCH;T11014 Numerical and ... 01.04.2009;; 1. Algebra, Geometry and ...
We present a robust and efficient algorithm for the pairwise non-rigid ... of time-varying geometry ... approximation of 3D shapes for ...
... Kimmel R.: Symmetries of non-rigid shapes. In ... Symposium on Geometry Processing, July 15-17, 2009, ... convex approximation of 3D shapes for fast ...
... Michael M. Bronstein; Ron Kimmel";Numerical Geometry of Non-Rigid Shapes;; ... Computational Geometry;;;;2009;635 ... Approximation Approach, Y ...
buku 105c Astrophysical ... Robert Jones 2009 Cambridge University Press ... Numerical geometry of non-rigid shapes Monographs in Computer Science ...