event thumbnail image
Machine Learning Summer School on Theory and Practice of Computational Learning

Cut Locus and Topology from Point Data

author: Tamal Dey, Department of Computer Science and Engineering, Ohio State University

Description

A cut locus of a point p in a compact Riemannian manifold M is defined as the set of points where minimizing geodesics issued from p stop being minimizing. It is known that a cut locus contains most of the topological information of M. Our goal is to utilize this property of cut loci to decipher the topology of M from a point sample. Recently it has been shown that Rips complexes can be built from a point sample P of M systematically to compute the Betti numbers, the rank of the homology groups of M. Rips complexes can be computed easily and therefore are favored over others such as restricted Delaunay, alpha, Cech, and witness complex. However, the sizes of the Rips complexes tend to be large. Since the dimension of a cut locus is lower than that of the manifold M, a subsample of P approximating the cut locus is usually much smaller in size and hence admits a relatively small Rips complex. In this talk we explore the above approach for point data sampled from surfaces embedded in any high dimensional Euclidean space. We present an algorithm that computes a subsample P' of a sample P of a 2-manifold where P' approximates a cut locus. Empirical results show that the first Betti number of M can be computed from the Rips complexes built on these subsamples. The sizes of these Rips complexes are much smaller than the one built on the original sample of M.

You might be experiencing some problems with Your Video player.
Slides
0:00 Cut Locus and Topology from Point Data
0:26 Problem (1)
0:52 Problem (2)
2:02 Motivations (1)
3:49 Motivations (2)
4:50 Motivations (3)
5:02 Motivations (4)
5:45 Motivations (5)
5:49 Motivations (6)
6:03 Motivations (7)
7:37 Motivations (8)
9:10 Motivations (9)
9:19 A Critical Observation (1)
10:09 A Critical Observation (2)
11:34 Goal (1)
12:26 Goal (2)
12:43 Goal (3)
13:07 Geodesics and Cut Locus (1)
13:23 Geodesics and Cut Locus (2)
14:56 Geodesics and Cut Locus (3)
15:11 Geodesics and Cut Locus (4)
15:25 Cut Locus (1)
15:38 Cut Locus (2)
16:18 Geodesics and Cut Locus – distances (1)
16:27 Geodesics and Cut Locus – distances (2)
16:33 Geodesics and Cut Locus – distances (3)
16:35 Geodesics and Cut Locus – distances (4)
16:41 Injectivity Radius (1)
17:18 Injectivity Radius (2)
18:00 Surface Cut Locus – structural properties (1)
18:29 Surface Cut Locus – structural properties (2)
19:17 Tree and Cycle Points (1)
19:21 Tree and Cycle Points (2)
19:39 Tree and Cycle Points (3)
20:17 Tree and Cycle Points (4)
20:28 A Structural Property
21:24 A Subset of C(p) (1)
22:03 A Subset of C(p) (2)
22:21 A Subset of C(p) (3)
22:51 A Subset of C(p) (4)
22:55 Geodesic Spread (1)
23:24 Geodesic Spread (2)
23:47 Geodesic Spread (3)
24:26 Geodesic Spread (4)
25:09 Geodesic Spread (5)
25:11 Geodesic Spread - example
25:52 Geodesic Spread and Cut Locus Points (1)
26:32 Geodesic Spread and Cut Locus Points (2)
26:49 Geodesic Spread and Cut Locus Points (3)
26:50 Geodesic Spread and Cut Locus Points (4)
27:53 Geodesic Spread and Cut Locus Points (5)
28:03 Approximating Geodesic Paths and Spread (1)
28:20 Approximating Geodesic Paths and Spread (2)
28:48 Approximating Geodesic Paths and Spread (3)
30:12 Approximating Geodesic Paths and Spread (4)
31:05 Geodesic Approximation (1)
32:01 Geodesic Approximation (2)
32:22 Geodesic Approximation (3)
32:50 Spread Approximation (1)
33:55 Spread Approximation (2)
34:22 Cut Locus Approximation
36:32 Cut Locus Approximation – justification of CUTLOCUS
38:17 Computing Homology – sampling density estimation (1)
38:45 Computing Homology – sampling density estimation (2)
39:46 Computing Homology – sampling density estimation (3)
39:57 Computing Homology – computing Betti numbers
40:40 Computing Homology – time complexity (1)
41:34 Computing Homology – time complexity (2)
41:57 Computing Homology – time complexity (3)
42:00 Experiments (1)
43:53 Experiments (2)
43:55 Experiments (3)
45:03 Experiments (4)
45:25 Experiments (5)
45:51 Experiments (6)
46:23 Experiments (7)
46:29 Conclusion and Future Work (1)
46:42 Conclusion and Future Work (2)
46:44 Conclusion and Future Work (3)
46:45 Conclusion and Future Work (4)
47:19 Conclusion and Future Work (5)
47:20 Thank you

Lecture rating

People found this lecture:
Worth seeing
because it is:
 Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: