Computational Topology

seminar

Alpha shapes

Celikik Marjan
Contents / Overview

1. Intuitive definition and applications

2. Formal definition

3. Construction of alpha-shapes (Edelsbrunner’s algorithm)

4. Dual definition, union of balls and homotopy equivalence

5. Limitations of classical alpha-shapes

6. Extensions
• Conformal Alpha-Shapes
• Weighted-Alpha Shapes

Computational Topology Alpha Shapes

Intuitive definition

What are α-shapes ?

Originally introduced by:

H. Edelsbrunner, D. G. Kirckpatrick and R. Seidel. On the shape of a set of points in the plane

Approach to formalize the intuitive notion of "shape" for spatial point sets

Generalization of the convex hull of a point set

Family of shapes derived from the Delaunay triangulation

parametarized by α

Dual shape* of the union of balls …

Computational Topology Alpha Shapes

Intuitive definition

Assume a finite set of points in the plane

We have a intuitive notion of the shape formed by these points

Computational Topology Alpha Shapes

Intuitive definition

α →∞ Sα ≡ convS

α →0 Sα ≡ S

Computational Topology Alpha Shapes

Applications

• Surface reconstruction and geometric modeling (later more)

Computational Topology Alpha Shapes

Applications

• Modeling molecular structures (later more)

HIV-1 Protease

Computational Topology Alpha Shapes

Applications

• Classification and visualization

HIV-1 Protease

Computational Topology Alpha Shapes

Applications

• Grid generation

• Medical image analysis

• Visualizing the structure of earthquake data …

Computational Topology Alpha Shapes

Formal definition – boundary of alpha-shape

Let the points in S be in general position

def. In k-1 dimensional hyperplane lie at most k points …

T ⊂ S with | T |= k + 1 ≤ d + 1 , the polytope ∆ T = convT has dimension k

Then ∆ T is a k-simplex

Definition. α − ball : Open ball with radius α, where ∂b is the surface of the sphere
Definition. k-simplex ∆T is α-exposed if there exists an empty α − ball with T = ∂b ∩ S

…analogy with the ice-cream “scenario”?

Computational Topology Alpha Shapes

Formal definition – boundary of alpha-shape

Let Sα be our alpha-shape

Then the boundary ∂Sα consists of all k-simplices of S, which are α-exposed
∂S α = {∆ T | T ⊂ S , | T |≤ d and ∆ T is α − exposed}

But what exactly is our alpha-shape?

Does it have a structure in space?

Or more formally…
Is there any polytope P such that ∂Sα = ∂P ?

later …

Computational Topology Alpha Shapes

Formal definition – Convex Hull and Delaunay Triangulation

Observation.

lim Sα = S lim Sα = convS

α →0 α →∞

Definiton. The Delaunay triangulation of S ⊂ R d is the simplicial complex DT(S) consisting of:

(i) All d-simplices such that their circumsphere does not contain any other points

(ii) All k-simplices which are faces of other simplices in DT(S)

Delaunay triangulation is the dual shape of the Voronoi diagram

Computational Topology Alpha Shapes

Formal definition – Delaunay Triangulation

Observation.

If ∆ T is an α-exposed simplex of S, then ∆ T ∈ DT (S )

Proof. (black-board)

Observation.

For any 0 ≤α ≤ ∞ Sα ⊂ DT (S )

This results allows us to construct simple algorithm for computing the alpha-shape

for each (d-1)-simplex ∆ T in DT(S)

if one of its circumspheres with radius α is empty
then ∆ T is α-exposed

…but what about lower dimensional simplices ?

infinitely many α-balls touching it

Computational Topology Alpha Shapes

Formal definition – Alpha Complex

Definition. The α-complex Cα (S ) is a simplicial subcomplex of DT(S).

A simplex ∆ T ∈ DT ( S ) is in Cα (S ) if

(i) it’s circumsphere is empty and has radius smaller than α , or

(ii) ∆ T is a face of another simplex in Cα (S )

We found a simplicial complex with boundary ∂Sα …

Result. The boundary of the α-complex is the boundary of the α-shape

There exist a polytope P, such that ∂Sα = ∂P, for all ∞ ≥ α ≥ 0

Computational Topology Alpha Shapes

Formal definition – Alpha Complex

One can prove:

∆ T ∈ ∂Sα ( S ) => ∆ T ∈ Cα ( S )

∆ T ∈ ∂Sα ( S ) => ∆ T ∈ ∂Cα ( S )

∆ T ∈ ∂Cα ( S ) => ∆ T ∈ ∂Sα ( S )

Finally:

∂Cα ( S ) = ∂Sα ( S )
Sα ( S ) ← Cα ( S )
The α-shape is the α-complex

Computational Topology Alpha Shapes

Formal definition – Interior of the alpha-shape

How to find the interior of an alpha-shape?

The straight-forward way:

Inspect the α-complex structure and check whether there is a d-simplex containing the facet

Another (better) way:

A facet ∆ T bounds the interior iff exactly one of the two α-balls with T = ∂b ∩ S is empty
Proof. (black-board)

Computational Topology Alpha Shapes

Formal definition

Observation.

α1 ≤ α 2 => Cα ( S ) ⊂ Cα ( S ) => Sα ( S ) ⊂ Sα ( S )
1 2 1 2

Proof.

According (i) α1 ≤ α 2 implies Cα1 ( S ) ⊂ Cα 2 ( S )

α-complex:
(i) it’s circumsphere is empty and has radius smaller than α , or
(ii) ∆ T is a face of another simplex in Cα (S )

Result.
This shows that for any simplex ∆ ∈ DT (S ) there is an interval I = [a, ∞ ]
and the simplex is in Cα (S ) iff α ∈I

Basis for Edelsbrunner’s Algorithm … (next)

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm - Intuitive

1. Compute the Delaunay triangulation of S knowing that it contains our α-shape

2. Compute Cα by inspecting all simplices ∆ T in DT ( S ) :

if its circumsphere is empty with smaller radius than α then
accept it (as well as all of its faces)

3. All d-simplices of Cα make up the interior of Sα. All simplices on the

boundary ∂Cα form ∂Sα

We need certain “primitives” to make the algorithm work:

• Delaunay triangulation (easy)

• Test of “emptiness” (easy)

• Whether a simplex lies on the boundary or inside ?

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm

Whether a simplex lies on the boundary or inside ?

1. If ∆ T ∈ convS then it must lie on the boundary

2. If all d-simplices containing it lie in Cα , then its inside

Let’s increase α from 0 to infinity and let ∆ T ∈ DT ( S ) ,

for all ∆ T ∈ DT ( S )

The algorithm computes all possible α-shapes for S

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm

Case 1: d-dimensional simplex (trivial)

Cannot be on the boundary: a = b = radius of its circumsphere

Case 2: k-dimensional simplex (k<d)

Idea: compute interval of k-simplex using already computed intervals for (k+1)-simplices.

α-complex:

(i) it’s circumsphere is empty and has radius smaller than α , or

(ii) ∆ T is a face of another simplex in Cα (S )

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm

∆T

Observation. Let ∆ T ∈ DT (S )

α-complex:

(i) it’s circumsphere is empty and has radius smaller than α , or

(ii) ∆ T is a face of another simplex in Cα (S )

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm

If ∆ T ∈ convS then it must lie on the boundary

∆T

Observation. Let ∆ T ∈ C S (α )

Then ∆ T ∈ interior of C S (α ) iff α ∈ (b, ∞)

Whether a simplex lies on the boundary or inside

1. If ∆ T ∈ convS then it must lie on the boundary

2. If all d-simplices containing it lie in Cα , then its inside

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm

Computational Topology Alpha Shapes

Edelsbrunner’s Algorithm – complexity concerns

Two dimensions.

Delaunay triangulation doable in O ( n log n) time

The number of simplices (faces) is O (n)

d dimensions.

The number of simplices is Θ( n|( d −1) / 2| ) !

Computational Topology Alpha Shapes

Union of balls

α−shapes are tightly related to another type of shape: The union of d-dimensional balls
Connection to be established soon…

Let B be a set of n d-balls in R d

Union of balls important for modeling molecules in chemistry and biology

Computational Topology Alpha Shapes

Union of balls – The three primal diagrams

pb = {x ∈ R d : || x − b ||≤ || x − b' ||, b'∈ B} - voronoi cell

qb = pb ∩ b - intersection of the cell with its ball

pT = b∈T
pb

qT = b∈T
qb

P = P ( B ) = { pT | ∅ ≠ T ⊆ B} The power diagram of B (generalization of the Voronoi diagram)

D = D( B ) = {qT | ∅ ≠ T ⊆ B} Intersection of P with U

U = U ( B) = b∈B
b The union of the balls

Computational Topology Alpha Shapes

Union of balls – The three primal diagrams

pb qb

P = P ( B ) = { pT | ∅ ≠ T ⊆ B} D = D( B ) = {qT | ∅ ≠ T ⊆ B} U = U ( B) = b
b∈B

| P |= pT = R d | D |= U
pT ∈P

Computational Topology Alpha Shapes

Union of balls – The three dual diagrams

Definition. Nerve of a collection of sets A is N ( A) = { X ⊆ A | a ≠ ∅}

a∈ X

All subsets of A with non-empty intersection (thus N(A) is an abstract simplicial complex)

Example: The nerve of B is the collection of all subsets of d-balls with non-empty common intersection

This triangle is empty

Geometric realization of the nerve of a set of balls

Computational Topology Alpha Shapes

Union of balls – The three dual diagrams

σ T ≡ Convex hull of the centers of the d-balls in T (actually the corresponding simplex convT)

R = R ( B ) = {σ T | ∅ ≠ pT ∈ P} ∪ {∅} The regular triangulation of B (Delaunay triangulation)

K = K ( B) = {σ T | ∅ ≠ qT ∈ D} ∪ {∅} The dual complex of D

S = S ( B ) =| K | The dual shape of U

R and K are geometric realizations of the nerves of P, D

P = P ( B ) = { pT | ∅ ≠ T ⊆ B}
D = D( B ) = {qT | ∅ ≠ T ⊆ B}
U = U ( B) = b∈B
b
Computational Topology Alpha Shapes
Union of balls – The three dual diagrams

P = P ( B ) = { pT | ∅ ≠ T ⊆ B} D = D( B ) = {qT | ∅ ≠ T ⊆ B} U = U ( B) = b =| D |
b∈B

pT ∈ P ⇔ σ T ∈ R

R = R ( B ) = {σ T | ∅ ≠ pT ∈ P} ∪ {∅} K = K ( B ) = {σ T | ∅ ≠ qT ∈ D} ∪ {∅} S = S ( B ) =| K |

Computational Topology Alpha Shapes

Union of balls – Another definition of alpha-shapes

dual

U = U ( B) = b =| D | S = S ( B ) =| K |
b∈B

Boundary of this complex is the boundary

of an α-shape* !

Alpha shape is the nerve of the union of balls intersected with their respective voronoi cells

Anybody noticing any difference with the previous definition? :-)

Computational Topology Alpha Shapes

Union of balls – Another definition of alpha-shapes

Computational Topology Alpha Shapes

Union of balls – Homotopy Equivalence

Result. They are homotopy equivalent!

S captures the basic topology of the union (but independently of dimension)

Deformation retraction. S is a deformation retraction of U

Intuitively, continuous deformation of the space until becomes the subspace without moving…
Special case of homotopy (the requirement of subspace is relaxed here)

Computational Topology Alpha Shapes

Union of balls – Algorithmic implications of homotopy equivalence

For a topological space Y, the k-th homology group H k = H k (Y ) is an abelian group that
expresses the k-dimensional connectivity of Y

Theorem. Two homotopy equivalent topological spaces have isomorphic homology groups.

Fact. There are very well known and efficient algorithms for computing homology groups of
simplicial complexes.

Result. We have an efficient algorithm for computing the homology groups for the union of
balls!

Computational Topology Alpha Shapes

Union of balls – Algorithmic implications of homotopy equivalence

The Union of balls as a model for various molecules has

• Combinatorial
• Metric
• Topological properties
• Folding, Connectivity …

…directly computable from the α-shape which is computationally inexpensive

Examples:

• Counting faces of the union of balls

• Measuring the union of balls (ex. volume)

• Physical forces associated with the molecules etc.

Computational Topology Alpha Shapes

Limitations of classical alpha shapes

Shape modeling.
Reconstruction of objects which have been sampled by points.

How to determine the “best” α ?

Computational Topology Alpha Shapes

Limitations of classical alpha shapes

There are sets of points for which no satisfying α exists

• Low density point-set will require large α in order to connect...

• Non-uniform distribution of points not appropriate

Computational Topology Alpha Shapes

Extensions – weighted alpha shapes

Generalization of α-shapes (the dual of the union of balls)

Each point has a weight assigned, α-shapes: all weights set to 0
Intuitively weights corresponds to radii of the balls

Again weighted alpha shape (again) is a polytope whose boundary is the union of all α-exposed
simplices spanned by S
Different definition of α-exposed simplex

Solves the problem of classical α-shapes for non-uniform density of sample points

Problem: How to assign the weights?

Computational Topology Alpha Shapes

Extensions – conformal alpha shapes

Conformal α-shape. Use a local scale parameter α̂ instead of the global scale parameter α
Used for reconstructing 3-dimensional smooth surfaces from a finite sampling…

At each point p in S we put a ball of radius α p determined from its internal alpha scale:

α p (αˆ ) = α p+αˆ + α p− α p+ =|| p − p * || α p− = α 1p = 0

Let C α̂p be the intersection of the voronoi cell and the ball at p, and let C α̂ be the interior of C α̂p
p∈P

Then conformal alpha complex is the Delaunay triangulation restricted to C α̂

Also a filtration of the Delaunay triangulation DT(S)

Computational Topology Alpha Shapes

Extensions – conformal alpha shapes

Computational Topology Alpha Shapes