Numerical geometry of non-rigid shapes (Stanford, winter 2009) - Consistent metric approximation in graphs

0 %
100 %
Information about Numerical geometry of non-rigid shapes (Stanford, winter 2009) -...
Technology

Published on January 29, 2009

Author: mike_br80

Source: slideshare.net

Description

Consistent metric approximation - Main idea - Sampling conditions - Surface properties - Sufficient conditions for consistency (Bernstein-de Silva-Langford-Tenenbaum theorem) - Why both conditions are important? - Probabilistic version

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

Sampling quality

Graph connectivity

Surface properties

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

-neighborhood connectivity

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

Connectivity

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

Add a comment

Related presentations

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...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

1 Numerical geometry of non-rigid shapes Consistent ...

3 Numerical geometry of non-rigid shapes Consistent approximation of geodesics in graphs Consistent metric approximation ... graphs Consistent ...
Read more

Consistent approximation of geodesics in graphs

Consistent approximation of geodesics in graphs ... Numerical geometry of non-rigid shapes ... of geodesics in graphs 3 Consistent metric approximation
Read more

1 Numerical geometry of non-rigid shapes Shortest path ...

1 Numerical geometry of non-rigid shapes Shortest path problems Shortest path problems Lecture 2 © Alexander & Michael Bronstein tosca.cs.technion.ac.il ...
Read more

Slide 1 - Israel Institute of Technology

Numerical geometry of non-rigid shapes Stanford ... the graph Consistent metric approximation Find a ... in graphs * * * * Numerical geometry of non ...
Read more

www.springer.com

... and begins his treatment by introducing such modern concepts as a metric ... KCH;T11014 Numerical and ... 01.04.2009;; 1. Algebra, Geometry and ...
Read more

Non-rigid registration under isometric deformations

We present a robust and efficient algorithm for the pairwise non-rigid ... of time-varying geometry ... approximation of 3D shapes for ...
Read more

Global intrinsic symmetries of shapes

... Kimmel R.: Symmetries of non-rigid shapes. In ... Symposium on Geometry Processing, July 15-17, 2009, ... convex approximation of 3D shapes for fast ...
Read more

www.springer.com

... Michael M. Bronstein; Ron Kimmel";Numerical Geometry of Non-Rigid Shapes;; ... Computational Geometry;;;;2009;635 ... Approximation Approach, Y ...
Read more

buku 105c - Lumbungbuku.com

buku 105c Astrophysical ... Robert Jones 2009 Cambridge University Press ... Numerical geometry of non-rigid shapes Monographs in Computer Science ...
Read more