 # 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

 User name: Comment:

## Related presentations #### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ... #### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna... #### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM #### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro #### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis... #### All you need to know about the Microsoft Band

November 6, 2014

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

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

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

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

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

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

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