Motivation

Eﬃcient Computation of Area-Minimizing Surfaces 2/ 26

Motivation

Eﬃcient Computation of Area-Minimizing Surfaces 2/ 26

Motivation

Eﬃcient Computation of Area-Minimizing Surfaces 2/ 26

Motivation

Eﬃcient Computation of Area-Minimizing Surfaces 2/ 26

Motivation

Figure: © Wikimedia user M(e)ister Eiskalt licensed

under CC BY 3.0. Image Courtesy of M(e)ister Eiskalt

Eﬃcient Computation of Area-Minimizing Surfaces 3/ 26

Motivation

Figure: © Wikimedia user M(e)ister Eiskalt licensed

under CC BY 3.0. Image Courtesy of M(e)ister Eiskalt

Eﬃcient Computation of Area-Minimizing Surfaces 3/ 26

Approach

Mathematical View

1. Take a sequence of surfaces with areas

decreasing to inﬁmum

2. Extract a convergent subsequence

3. Show that the limit surface is the desired

surface of least area

Computer Science View

1. Guess any initial mesh

2. Create optimization problem with area as

cost function

3. Show that the limit surface is the desired

surface of least area

Eﬃcient Computation of Area-Minimizing Surfaces 4/ 26

Approach

Mathematical View

1. Take a sequence of surfaces with areas

decreasing to inﬁmum

2. Extract a convergent subsequence

3. Show that the limit surface is the desired

surface of least area

Computer Science View

1. Guess any initial mesh

2. Create optimization problem with area as

cost function

3. Show that the limit surface is the desired

surface of least area

Eﬃcient Computation of Area-Minimizing Surfaces 4/ 26

Approach

Mathematical View

1. Take a sequence of surfaces with areas

decreasing to inﬁmum

2. Extract a convergent subsequence

3. Show that the limit surface is the desired

surface of least area

Computer Science View

1. Guess any initial mesh

2. Create optimization problem with area as

cost function

3. Show that the limit surface is the desired

surface of least area

Eﬃcient Computation of Area-Minimizing Surfaces 4/ 26

Approach

Mathematical View

1. Take a sequence of surfaces with areas

decreasing to inﬁmum

2. Extract a convergent subsequence

3. Show that the limit surface is the desired

surface of least area

Computer Science View

1. Guess any initial mesh

2. Create optimization problem with area as

cost function

3. Show that the limit surface is the desired

surface of least area

Eﬃcient Computation of Area-Minimizing Surfaces 4/ 26

1. Math Lecture: Exterior Algebra

▶

0-Vector has Orientation and Magnitude

has dimension 1

▶

1-Vector has Orientation and Magnitude

has dimension 3

▶

2-Vector has Orientation and Magnitude

has dimension 3

▶

3-Vector has Orientation and Magnitude

has dimension 1

Figure: u ∈ Λ

Eﬃcient Computation of Area-Minimizing Surfaces 5/ 26

1. Math Lecture: Exterior Algebra

▶

0-Vector has Orientation and Magnitude

has dimension 1

▶

1-Vector has Orientation and Magnitude

has dimension 3

▶

2-Vector has Orientation and Magnitude

has dimension 3

▶

3-Vector has Orientation and Magnitude

has dimension 1

Figure: u ∧ v ∈ Λ

Eﬃcient Computation of Area-Minimizing Surfaces 5/ 26

1. Math Lecture: Exterior Algebra

▶

0-Vector has Orientation and Magnitude

has dimension 1

▶

1-Vector has Orientation and Magnitude

has dimension 3

▶

2-Vector has Orientation and Magnitude

has dimension 3

▶

3-Vector has Orientation and Magnitude

has dimension 1

Figure: u ∧ v ∧ w ∈ Λ

Eﬃcient Computation of Area-Minimizing Surfaces 5/ 26

1. Math Lecture: Exterior Algebra

▶

0-Vector has Orientation and Magnitude

has dimension 1

▶

1-Vector has Orientation and Magnitude

has dimension 3

▶

2-Vector has Orientation and Magnitude

has dimension 3

▶

3-Vector has Orientation and Magnitude

has dimension 1

Figure: s ∈ Λ

Eﬃcient Computation of Area-Minimizing Surfaces 5/ 26

1. Math Lecture: Exterior Algebra

k-vector space denoted by Λ

is itself a vector space of dimension





▶

Basis for Λ

{1}

▶

Basis for Λ

, b

}

▶

Basis for Λ

∧ b

, b

∧ b

, b

∧ b

}

▶

Basis for Λ

∧ b

}

Eﬃcient Computation of Area-Minimizing Surfaces 6/ 26

1. Math Lecture: Exterior Algebra

k-vector space denoted by Λ

is itself a vector space of dimension





▶

Basis for Λ

{1}

▶

Basis for Λ

, b

}

▶

Basis for Λ

∧ b

, b

∧ b

, b

∧ b

}

▶

Basis for Λ

∧ b

}

Figure: 5 = 5 · 1

Eﬃcient Computation of Area-Minimizing Surfaces 6/ 26

1. Math Lecture: Exterior Algebra

k-vector space denoted by Λ

is itself a vector space of dimension





▶

Basis for Λ

{1}

▶

Basis for Λ

, b

}

▶

Basis for Λ

∧ b

, b

∧ b

, b

∧ b

}

▶

Basis for Λ

∧ b

}

−1 · b

0.5 · b

0.8 · b

Eﬃcient Computation of Area-Minimizing Surfaces 6/ 26

1. Math Lecture: Exterior Algebra

k-vector space denoted by Λ

is itself a vector space of dimension





▶

Basis for Λ

{1}

▶

Basis for Λ

, b

}

▶

Basis for Λ

∧ b

, b

∧ b

, b

∧ b

}

▶

Basis for Λ

∧ b

}

1 · (b

∧ b

)

−0.8 · (b

∧ b

)

−0.6 · (b

∧ b

)

Eﬃcient Computation of Area-Minimizing Surfaces 6/ 26

1. Math Lecture: Exterior Algebra

k-vector space denoted by Λ

is itself a vector space of dimension





▶

Basis for Λ

{1}

▶

Basis for Λ

, b

}

▶

Basis for Λ

∧ b

, b

∧ b

, b

∧ b

}

▶

Basis for Λ

∧ b

}

Eﬃcient Computation of Area-Minimizing Surfaces 6/ 26

1. Math Lecture: Exterior Algebra

Eﬃcient Computation of Area-Minimizing Surfaces 7/ 26

1. Math Lecture: Exterior Algebra

k-forms space Λ

is the dual space of Λ

, i.e. the space of all linear functions from Λ

to R.

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

▶

For u, v ∈ Λ

the inner product is:

⟨u

∧ . . . ∧ u

, v

∧ . . . ∧ v

⟩ = det(⟨u

, v

⟩)

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

Eﬃcient Computation of Area-Minimizing Surfaces 8/ 26

1. Math Lecture: Exterior Algebra

k-forms space Λ

is the dual space of Λ

, i.e. the space of all linear functions from Λ

to R.

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

▶

For u, v ∈ Λ

the inner product is:

⟨u

∧ . . . ∧ u

, v

∧ . . . ∧ v

⟩ = det(⟨u

, v

⟩)

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

Eﬃcient Computation of Area-Minimizing Surfaces 8/ 26

1. Math Lecture: Exterior Algebra

k-forms space Λ

is the dual space of Λ

, i.e. the space of all linear functions from Λ

to R.

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

▶

For u, v ∈ Λ

the inner product is:

⟨u

∧ . . . ∧ u

, v

∧ . . . ∧ v

⟩ = det(⟨u

, v

⟩)

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

Eﬃcient Computation of Area-Minimizing Surfaces 8/ 26

1. Math Lecture: Exterior Algebra

k-forms space Λ

is the dual space of Λ

, i.e. the space of all linear functions from Λ

to R.

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

▶

For u, v ∈ Λ

the inner product is:

⟨u

∧ . . . ∧ u

, v

∧ . . . ∧ v

⟩ = det(⟨u

, v

⟩)

▶

Fix any v ∈ Λ

: Λ

→ R := x 7→ ⟨v, x⟩

Eﬃcient Computation of Area-Minimizing Surfaces 8/ 26

1. Math Lecture: Exterior Algebra

k-form space denoted by Λ

is itself a vector space of dimension





▶

Note that since







n−k



▶

we deﬁne the hodge star operator mapping

→ Λ

n−k

▶

such that ⋆ ⋆ u = (−1)

k(n−k)u

Eﬃcient Computation of Area-Minimizing Surfaces 9/ 26

1. Math Lecture: Exterior Algebra

k-form space denoted by Λ

is itself a vector space of dimension





▶

Note that since







n−k



▶

we deﬁne the hodge star operator mapping

→ Λ

n−k

▶

such that ⋆ ⋆ u = (−1)

k(n−k)u

Eﬃcient Computation of Area-Minimizing Surfaces 9/ 26

1. Math Lecture: Exterior Algebra

k-form space denoted by Λ

is itself a vector space of dimension





▶

Note that since







n−k



▶

we deﬁne the hodge star operator mapping

→ Λ

n−k

▶

such that ⋆ ⋆ u = (−1)

k(n−k)u

Eﬃcient Computation of Area-Minimizing Surfaces 9/ 26

1. Math Lecture: Exterior Algebra

k-form space denoted by Λ

is itself a vector space of dimension





▶

Note that since







n−k



▶

we deﬁne the hodge star operator mapping

→ Λ

n−k

▶

such that ⋆ ⋆ u = (−1)

k(n−k)u

Eﬃcient Computation of Area-Minimizing Surfaces 9/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Calculus to k-vectors on smooth manifolds.

Scalar ﬁeld: R

→ R

Vector ﬁeld: R

→ R

Eﬃcient Computation of Area-Minimizing Surfaces 10/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Calculus to k-vectors on smooth manifolds.

0-vector ﬁeld: R

→ Λ

1-vector ﬁeld: R

→ Λ

diﬀerential 0-form: R

→ Λ

diﬀerential 1-form: R

→ Λ

Eﬃcient Computation of Area-Minimizing Surfaces 10/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Calculus to k-vectors on smooth manifolds.

→ (Λ

→ R))

| {z }

diﬀerential 2-form

→ Λ

)

| {z }

2-vec ﬁeld

→ (R

→ R)

| {z }

scalarf ield

Eﬃcient Computation of Area-Minimizing Surfaces 10/ 26

2. Math Lecture: Exterior Calculus

▶

n-manifold M :

space that locally look like Euclidean Space .

▶

smooth n-manifold:

smoothly compatible charts

▶

allows deﬁnition of tangent spaces.

▶

allows deﬁnition of smooth vector ﬁelds X(M)

▶

allows deﬁnition of form-ﬁelds called

diﬀerential forms denoted by Ω

(M)

▶

allows deﬁnition of integrals of ω ∈ Ω

(M):

ω =

ω(dV )

Eﬃcient Computation of Area-Minimizing Surfaces 11/ 26

2. Math Lecture: Exterior Calculus

▶

n-manifold M :

space that locally look like Euclidean Space .

▶

smooth n-manifold:

smoothly compatible charts

▶

allows deﬁnition of tangent spaces.

▶

allows deﬁnition of smooth vector ﬁelds X(M)

▶

allows deﬁnition of form-ﬁelds called

diﬀerential forms denoted by Ω

(M)

▶

allows deﬁnition of integrals of ω ∈ Ω

(M):

ω =

ω(dV )

Eﬃcient Computation of Area-Minimizing Surfaces 11/ 26

2. Math Lecture: Exterior Calculus

▶

n-manifold M :

space that locally look like Euclidean Space .

▶

smooth n-manifold:

smoothly compatible charts

▶

allows deﬁnition of tangent spaces.

▶

allows deﬁnition of smooth vector ﬁelds X(M)

▶

allows deﬁnition of form-ﬁelds called

diﬀerential forms denoted by Ω

(M)

▶

allows deﬁnition of integrals of ω ∈ Ω

(M):

ω =

ω(dV )

Eﬃcient Computation of Area-Minimizing Surfaces 11/ 26

2. Math Lecture: Exterior Calculus

▶

n-manifold M :

space that locally look like Euclidean Space .

▶

smooth n-manifold:

smoothly compatible charts

▶

allows deﬁnition of tangent spaces.

▶

allows deﬁnition of smooth vector ﬁelds X(M)

▶

allows deﬁnition of form-ﬁelds called

diﬀerential forms denoted by Ω

(M)

▶

allows deﬁnition of integrals of ω ∈ Ω

(M):

ω =

ω(dV )

Eﬃcient Computation of Area-Minimizing Surfaces 11/ 26

2. Math Lecture: Exterior Calculus

▶

n-manifold M :

space that locally look like Euclidean Space .

▶

smooth n-manifold:

smoothly compatible charts

▶

allows deﬁnition of tangent spaces.

▶

allows deﬁnition of smooth vector ﬁelds X(M)

▶

allows deﬁnition of form-ﬁelds called

diﬀerential forms denoted by Ω

(M)

▶

allows deﬁnition of integrals of ω ∈ Ω

(M):

ω =

ω(dV )

Eﬃcient Computation of Area-Minimizing Surfaces 11/ 26

2. Math Lecture: Exterior Derivative

d(ω) =

i=1

∂

ω β

partial derivative w.r.t. the ith coordinate

ω ∈ Ω

coordinate basis form

d(ω) =

i,j

∂

(β

∧ β

)

partial derivative w.r.t. the ith coordinate

coordinate basis form

ω ∈ Ω

jth component

Eﬃcient Computation of Area-Minimizing Surfaces 12/ 26

2. Math Lecture: Exterior Derivative

d(ω) =

i=1

∂

ω β

partial derivative w.r.t. the ith coordinate

ω ∈ Ω

coordinate basis form

d(ω) =

i,j

∂

(β

∧ β

)

partial derivative w.r.t. the ith coordinate

coordinate basis form

ω ∈ Ω

jth component

Eﬃcient Computation of Area-Minimizing Surfaces 12/ 26

2. Math Lecture: Exterior Derivative

grad(f)

∼

(d)(f) curl(X)

∼

(⋆d )(X) div(X)

∼

(⋆d⋆)(X)

∞

) X(R

) C

∞

)

Ω

) Ω

)

grad

curl div

d d d

⋆ ⋆

⟲ ⟲ ⟲

Eﬃcient Computation of Area-Minimizing Surfaces 13/ 26

2. Math Lecture: Exterior Derivative

grad(f)

∼

(d)(f) curl(X)

∼

(⋆d )(X) div(X)

∼

(⋆d⋆)(X)

∞

) X(R

) C

∞

)

Ω

) Ω

)

grad

curl div

d d d

⋆ ⋆

⟲ ⟲ ⟲

Eﬃcient Computation of Area-Minimizing Surfaces 13/ 26

2. Math Lecture: Exterior Derivative

Overall, we deﬁne the exterior derivative to be the

unique operator:

d : Ω

→ Ω

k+1

T M (1)

for all k that satisfy the following properties:

(i) d is linear over R, that is d(ω + η) = dω + dη.

(ii) If ω ∈ Ω

(M) and η ∈ Ω

(M), then

d(ω ∧ η) = dω ∧ n + (−1)

ω ∧ dη.

(iii) d ◦ d ≡ 0

(iv) For f ∈ Ω

(M) = C

∞

(M), df is the

diﬀerential of f, given by df(X) = X(f) for

any X.

Eﬃcient Computation of Area-Minimizing Surfaces 14/ 26

2. Math Lecture: Exterior Derivative

Overall, we deﬁne the exterior derivative to be the

unique operator:

d : Ω

→ Ω

k+1

T M (1)

for all k that satisfy the following properties:

(iii) d ◦ d ≡ 0

We call a diﬀerential form ω ∈ Ω

▶

closed if dω ≡ 0.

▶

exact if ω ≡ dη

for any η ∈ Ω

k−1

(M).

Eﬃcient Computation of Area-Minimizing Surfaces 14/ 26

2. Math Lecture: Exterior Derivative

Overall, we deﬁne the exterior derivative to be the

unique operator:

d : Ω

→ Ω

k+1

T M (1)

for all k that satisfy the following properties:

(iii) d ◦ d ≡ 0

We call a diﬀerential form ω ∈ Ω

▶

closed if dω ≡ 0.

▶

exact if ω ≡ dη

for any η ∈ Ω

k−1

(M).

Eﬃcient Computation of Area-Minimizing Surfaces 14/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Integral Calculus

▶

Gradient Theorem:

grad(ω)(r) · dr = ω(p) − ω(q)

▶

Generalizes smooth n-Manifold to

smooth n-Manifold with boundary

▶

∂M is smooth (n − 1)-manifold without

boundary

▶

Stokes Theorem:

dω =

∂M

ω,

where M smooth n-manifold with boundary

and ω is smooth diﬀerential (n-1)-form

Eﬃcient Computation of Area-Minimizing Surfaces 15/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Integral Calculus

▶

Gradient Theorem:

grad(ω)(r) · dr = ω(p) − ω(q)

▶

Generalizes smooth n-Manifold to

smooth n-Manifold with boundary

▶

∂M is smooth (n − 1)-manifold without

boundary

▶

Stokes Theorem:

dω =

∂M

ω,

where M smooth n-manifold with boundary

and ω is smooth diﬀerential (n-1)-form

∂

∈ R

∈ H

∈ R

Eﬃcient Computation of Area-Minimizing Surfaces 15/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Integral Calculus

▶

Gradient Theorem:

grad(ω)(r) · dr = ω(p) − ω(q)

▶

Generalizes smooth n-Manifold to

smooth n-Manifold with boundary

▶

∂M is smooth (n − 1)-manifold without

boundary

▶

Stokes Theorem:

dω =

∂M

ω,

where M smooth n-manifold with boundary

and ω is smooth diﬀerential (n-1)-form

∂

∈ R

∈ H

∈ R

Eﬃcient Computation of Area-Minimizing Surfaces 15/ 26

2. Math Lecture: Exterior Calculus

Generalize Vector Integral Calculus

▶

Gradient Theorem:

grad(ω)(r) · dr = ω(p) − ω(q)

▶

Generalizes smooth n-Manifold to

smooth n-Manifold with boundary

▶

∂M is smooth (n − 1)-manifold without

boundary

▶

Stokes Theorem:

dω =

∂M

ω,

where M smooth n-manifold with boundary

and ω is smooth diﬀerential (n-1)-form

∂

∈ R

∈ H

∈ R

Eﬃcient Computation of Area-Minimizing Surfaces 15/ 26

Recap

▶

vectors → k-vectors

▶

k-vectors → k-forms

▶

⋆:k-vectors → orthonagonal component

▶

vector ﬁeld → diﬀerential k-forms

▶

grad, curl, div → exterior derivative

▶

Gradient Theorem → Stokes Theorem

Eﬃcient Computation of Area-Minimizing Surfaces 16/ 26

Recap

▶

vectors → k-vectors

▶

k-vectors → k-forms

▶

⋆:k-vectors → orthonagonal component

▶

vector ﬁeld → diﬀerential k-forms

▶

grad, curl, div → exterior derivative

▶

Gradient Theorem → Stokes Theorem

Eﬃcient Computation of Area-Minimizing Surfaces 16/ 26

Recap

▶

vectors → k-vectors

▶

k-vectors → k-forms

▶

⋆:k-vectors → orthonagonal component

▶

vector ﬁeld → diﬀerential k-forms

▶

grad, curl, div → exterior derivative

▶

Gradient Theorem → Stokes Theorem

Eﬃcient Computation of Area-Minimizing Surfaces 16/ 26

Recap

▶

vectors → k-vectors

▶

k-vectors → k-forms

▶

⋆:k-vectors → orthonagonal component

▶

vector ﬁeld → diﬀerential k-forms

▶

grad, curl, div → exterior derivative

▶

Gradient Theorem → Stokes Theorem

Eﬃcient Computation of Area-Minimizing Surfaces 16/ 26

Recap

▶

vectors → k-vectors

▶

k-vectors → k-forms

▶

⋆:k-vectors → orthonagonal component

▶

vector ﬁeld → diﬀerential k-forms

▶

grad, curl, div → exterior derivative

▶

Gradient Theorem → Stokes Theorem

Eﬃcient Computation of Area-Minimizing Surfaces 16/ 26

Recap

▶

vectors → k-vectors

▶

k-vectors → k-forms

▶

⋆:k-vectors → orthonagonal component

▶

vector ﬁeld → diﬀerential k-forms

▶

grad, curl, div → exterior derivative

▶

Gradient Theorem → Stokes Theorem

Eﬃcient Computation of Area-Minimizing Surfaces 16/ 26

3. Math Lecture: Geometric Measure theory

How do we avoid this?

Eﬃcient Computation of Area-Minimizing Surfaces 17/ 26

3. Math Lecture: Geometric Measure theory

Measurement of Set

(A) = lim

δ→0

inf

A⊂∪S

diam(S

)≤δ



diam(S

)



where a

denote thes volume of closed m-unit ball B

and diam(S ) denotes the

diameter of any S ⊆ R

deﬁned by diam(S) = sup{|x − y| : x, y ∈ S}.

Deﬁnition of Surface

currents are sets that are diﬀerentiable almost

everywhere, that act on diﬀerentials forms by

S(φ) =

⟨

−→

S (x), φ⟩ dH

where

−→

S (x) denotes the unit k-form associated

with each tangent space.

Eﬃcient Computation of Area-Minimizing Surfaces 18/ 26

3. Math Lecture: Geometric Measure theory

Measurement of Set

(A) = lim

δ→0

inf

A⊂∪S

diam(S

)≤δ



diam(S

)



where a

denote thes volume of closed m-unit ball B

and diam(S ) denotes the

diameter of any S ⊆ R

deﬁned by diam(S) = sup{|x − y| : x, y ∈ S}.

Deﬁnition of Surface

currents are sets that are diﬀerentiable almost

everywhere, that act on diﬀerentials forms by

S(φ) =

⟨

−→

S (x), φ⟩ dH

where

−→

S (x) denotes the unit k-form associated

with each tangent space.

Eﬃcient Computation of Area-Minimizing Surfaces 18/ 26

3. Math Lecture: Geometric Measure theory

Results of geometric measure theory

▶

area-minimizing currents exist

▶

area-minimizing currents are smooth

embedded manifolds...

▶

but only up to dimension 8!

Eﬃcient Computation of Area-Minimizing Surfaces 19/ 26

3. Math Lecture: Geometric Measure theory

Results of geometric measure theory

▶

area-minimizing currents exist

▶

area-minimizing currents are smooth

embedded manifolds...

▶

but only up to dimension 8!

Eﬃcient Computation of Area-Minimizing Surfaces 19/ 26

3. Math Lecture: Geometric Measure theory

Results of geometric measure theory

▶

area-minimizing currents exist

▶

area-minimizing currents are smooth

embedded manifolds...

▶

but only up to dimension 8!

Eﬃcient Computation of Area-Minimizing Surfaces 19/ 26

3. Math Lecture: Geometric Measure theory

Results of geometric measure theory

▶

area-minimizing currents exist

▶

area-minimizing currents are smooth

embedded manifolds...

▶

but only up to dimension 8!

Eﬃcient Computation of Area-Minimizing Surfaces 19/ 26

3. Math Lecture: Geometric Measure theory

Results of geometric measure theory

(∂S)(ω) = S(dω)

Eﬃcient Computation of Area-Minimizing Surfaces 20/ 26

Discretization

minimize

S∈I

(S)

subject to

ω∈Ω

)

B(ω) = S(dω).

Discretize in grid - Assign k-vector at each vertex.

minimize

S∈bΩ

S||

subject to

ω∈Ω

)

B(ω) =

S(dω).

But this requires O(n

) time in each iteration.

Eﬃcient Computation of Area-Minimizing Surfaces 21/ 26

Discretization

minimize

S∈I

(S)

subject to

ω∈Ω

)

B(ω) = S(dω).

Discretize in grid - Assign k-vector at each vertex.

minimize

S∈bΩ

S||

subject to

ω∈Ω

)

B(ω) =

S(dω).

But this requires O(n

) time in each iteration.

Eﬃcient Computation of Area-Minimizing Surfaces 21/ 26

Discretization

minimize

S∈I

(S)

subject to

ω∈Ω

)

B(ω) = S(dω).

Discretize in grid - Assign k-vector at each vertex.

minimize

S∈bΩ

S||

subject to

ω∈Ω

)

B(ω) =

S(dω).

But this requires O(n

) time in each iteration.

Eﬃcient Computation of Area-Minimizing Surfaces 21/ 26

Discretization

With periodic boundary condition we would only need O(n log n) time

Eﬃcient Computation of Area-Minimizing Surfaces 22/ 26

Discretization

With periodic boundary condition we would only need O(n log n) time

Eﬃcient Computation of Area-Minimizing Surfaces 22/ 26

Discretization

With periodic boundary condition we would only need O(n log n) time

Eﬃcient Computation of Area-Minimizing Surfaces 22/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

∆

−1

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

∆

−1

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

(M)

v − u

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

− σ

∈ B

(M)

− σ

/∈ B

(M)

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

(M ): "vector space" generated by all σ : ∆

→ M .

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

∂

−−→ C

(M )

(M ) = ker(∂

)

(M ) = Im(∂

k+1

)

(M ) =

(M )

Ω

(M ): diﬀerentiable k-forms

Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

−−→ Ω

(M )

(M ) = ker(d

)

(M ) = Im(d

k+1

)

(M ) =

(M )

∆

−1

∈ Z

∈ B

∈ Z

/∈ B

∈ Z

/∈ B

− σ

∈ B

(M)

− σ

/∈ B

(M)

ec ∈ Z

(M)

b ∈ C

(M)

′

∈ Z

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 23/ 26

4. Math Lecture: Homology Theory

Codiﬀerential:

δ : Ω

(M) → Ω

k−1

(M) := ω 7→ (−1)

n(k+1)+1

(⋆d⋆)(ω),

so that we obtain the following maps between the spaces:

Ω

(M) Ω

(M)

Laplacian:

∆ : Ω

(M) → Ω

(M) := ω 7→ dδω + δdω

Harmonic forms:

∆

(M) =



ω ∈ Ω

(M) : ∆ω = 0



Hodge Decomposition:

Ω

(M)

∼

Imd

k−1

⊕ Imδ

k+1

⊕ H

∆

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 24/ 26

4. Math Lecture: Homology Theory

Codiﬀerential:

δ : Ω

(M) → Ω

k−1

(M) := ω 7→ (−1)

n(k+1)+1

(⋆d⋆)(ω),

so that we obtain the following maps between the spaces:

Ω

(M) Ω

(M)

Laplacian:

∆ : Ω

(M) → Ω

(M) := ω 7→ dδω + δdω

Harmonic forms:

∆

(M) =



ω ∈ Ω

(M) : ∆ω = 0



Hodge Decomposition:

Ω

(M)

∼

Imd

k−1

⊕ Imδ

k+1

⊕ H

∆

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 24/ 26

4. Math Lecture: Homology Theory

Codiﬀerential:

δ : Ω

(M) → Ω

k−1

(M) := ω 7→ (−1)

n(k+1)+1

(⋆d⋆)(ω),

so that we obtain the following maps between the spaces:

Ω

(M) Ω

(M)

Laplacian:

∆ : Ω

(M) → Ω

(M) := ω 7→ dδω + δdω

Harmonic forms:

∆

(M) =



ω ∈ Ω

(M) : ∆ω = 0



Hodge Decomposition:

Ω

(M)

∼

Imd

k−1

⊕ Imδ

k+1

⊕ H

∆

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 24/ 26

4. Math Lecture: Homology Theory

Codiﬀerential:

δ : Ω

(M) → Ω

k−1

(M) := ω 7→ (−1)

n(k+1)+1

(⋆d⋆)(ω),

so that we obtain the following maps between the spaces:

Ω

(M) Ω

(M)

Laplacian:

∆ : Ω

(M) → Ω

(M) := ω 7→ dδω + δdω

Harmonic forms:

∆

(M) =



ω ∈ Ω

(M) : ∆ω = 0



Hodge Decomposition:

Ω

(M)

∼

Imd

k−1

⊕ Imδ

k+1

⊕ H

∆

(M)

Eﬃcient Computation of Area-Minimizing Surfaces 24/ 26

Final Optimization Problem

Hodge Decomposition:

Ω

(M)

∼

Im(d

k−1

) ⊕ Im(δ

k+1

) ⊕ H

∆

(M)

homology class ﬁxes H

∆

(M), boundary condition ﬁxes Im(d

k−1

)

minimize

S∈I

,ω∈Ω

)

||S||

subject to δω − S = S

Discretize:

minimize

S∈bΩ

,ˆω∈bΩ

S||

subject to

δˆω −

S =

Eﬃcient Computation of Area-Minimizing Surfaces 25/ 26

Final Optimization Problem

Hodge Decomposition:

Ω

(M)

∼

Im(d

k−1

) ⊕ Im(δ

k+1

) ⊕ H

∆

(M)

homology class ﬁxes H

∆

(M), boundary condition ﬁxes Im(d

k−1

)

minimize

S∈I

,ω∈Ω

)

||S||

subject to δω − S = S

Discretize:

minimize

S∈bΩ

,ˆω∈bΩ

S||

subject to

δˆω −

S =

Eﬃcient Computation of Area-Minimizing Surfaces 25/ 26

Final Optimization Problem

Hodge Decomposition:

Ω

(M)

∼

Im(d

k−1

) ⊕ Im(δ

k+1

) ⊕ H

∆

(M)

homology class ﬁxes H

∆

(M), boundary condition ﬁxes Im(d

k−1

)

minimize

S∈I

,ω∈Ω

)

||S||

subject to δω − S = S

Discretize:

minimize

S∈bΩ

,ˆω∈bΩ

S||

subject to

δˆω −

S =

Eﬃcient Computation of Area-Minimizing Surfaces 25/ 26

Thank you

seminar report url: spooky.moe/d00

Eﬃcient Computation of Area-Minimizing Surfaces 26/ 26