Transcript ppt

Topology Preserving Edge Contraction
Paper By
Dr. Tamal Dey et al
Presented by
Ramakrishnan Kazhiyur-Mannar
Some Definitions (Lots actually)
Point – a d-dimensional point is a d-tuple of real
numbers.
Norm of a Point – If the point x = (x1, x2, x3…xd),
the norm ||x|| = (Sxi2)1/2
Euclidean Space – A d-dimensional Euclidean
space Rd is the set of d-dimensional points
together with the euclidean distance function
mapping each set of points (x,y) to ||x-y||.
More Definitions
d–1 sphere: Sd-1 = {x  Rd | ||x|| = 1}
1-Sphere – Circle, 2-Sphere-Sphere (hollow)
d-ball: Bd = {x  Rd | ||x||  1}
2-ball - Disk (curve+interior), 3-ball – Sphere (Solid)
The surface of a d-ball is a d-1 sphere.
d-halfspace: Hd = {x  Rd | x1 = 1}
Even More Definitions
Manifold: A d-manifold is a non-empty
topological space where at each point, the
neighborhood is either a Rd or a Hd.
With Boundary/ Without Boundary
Lots more Definitions 
k-Simplex is the convex hull of k+1 affinely
independent point k  0
Still more Definitions
Face: If s is a simplex a face of s, t is defined
by a non-empty subset of the k+1 points.
p0
p3
p1
Proper faces
Example of faces:
{p0}, {p1}, {p0, p0p1},
{p0, p1, p2, p0p1, p0p2, p1p2, p0p1p2}
p2
Definitions
(I have given up trying to get unique titles)
Coface: If t is a face of s, then s is a coface of
t, written as ts.
The interior of the simplex is the set of points
contained in s but not on any proper face of s.
Simplicial Complex
A collection of simplices, K, such that
if sK and ts, then tK i.e. for each face in K, all the
faces of it is there K and all their subfaces are there etc.
and
s, s’  K =>
 ss’ =f or
 ss’ s and ss’ s’
i.e. if two faces intersect, they intersect on their face.
Simplicial Complex
p0
p3
p1
Examples of a simplicial complex:
{p0}, {p0, p1, p2, p0p1}
{p0, p1, p2, p0p1, p0p2, p1p2, p0p1p2}
Examples of a non-simplicial complex:
{p0, p0p1}
p2
p0
Examples of a non-simplicial complex:
p4
{p0, p1, p2, p3, p4,
p0p1, p1p2, p2p0, p3p4}
p3
p1
p2
Subcomplex, Closure
A subcomplex of a simplicial complex one of its
subsets that is a simplicial complex in itself.
{p0, p1, p0p1} is a subcomplex of {p0, p1, p2, p0p1,
p1p2, p2p0, p0p1p2}
The Underlying space is the union of simplex
interiors. |K| = UsK int s
Closure
Let B  K (B need not be a subcomplex).
Closure of B is the set of all faces of simplices of B.
The Closure is the smallest subcomplex that
contains B.
p0
p1
p2
Star
The star of B is the set of all cofaces of simplices
in B.
Link
Link of B is the set of all faces of cofaces of
simplices in B that are disjoint from the simples
in B
Mathematically Speaking
B = {τ  K | τ  σ  B}
St B = {σ  K | σ  τ  B}
Lk B = St B - St B
Or Simply,
L
Subdivision
A subdivision of K is a complex Sd K such that
|Sd K| = |K| and
s K => sSd K
Homeomorphism
Homeomorphism is topological equivalence
An intuitive definition?
Technical definition: Homeomorphism between
two spaces X and Y is a bijection h:XY such
that both h and h’ are continuous.
If $ a Homeomorphism between two spaces
then they are homeomorphic X Y and are said
to be of the same topological type or genus.
Combinatorial Version
Complexes stand for topological spaces in
combinatorial domain.
A vertex map for two complexes K and L is a
function f: Vert KVert L.
A Simplicial Map f: |K||L| is defined by

u Vert K
bu ( x)  f (u )
Combinatorial Version (contd.)
f need not be injective or surjective.
It is a homeomorphism iff f is bijective and f -1 is
a vertex map.
Here, we call it isomorphism denoted by K ~ L.
There is a slight difference between isomorphism
and homeomorphism.
Order
Remember manifolds?
What if the neighborhood of a point is not a ball?
For s, a simplex in K, if dim St s = k, the order is
the smallest interger I for which there is a (k-i)
simplex hsuch that St s ~ St h
What is that mumbo-jumbo??
Order (contd.)
Boundary
The Jth boundary of a simplicial complex K is the
set of simplices with order no less than j.
Order Bound: Jth boundary can contain only
simplices of dimensions not more than dim K-j
Jth boundary contains (j+1)st Boundary.
This is used to have a hierarchy of complexes.
Edge Contraction (Finally!!)
In the Language of Math…
Contraction is a surjective simplicial map
jab:|K||L| defined by a surjective vertex map
f(u) =
u if u Vert K – {a, b}
c if u {a, b}
Outside |St ab|, the mapping is unity.
Inside, it is not even injective.
One Last Term…
An unfolding i of jab is a simplicial
homeomorphism |K|  |L|.
It is local if it differs from jab only inside |E| and it
is relaxed if it differs from jab only inside |St E|
Now, WHAT IS THAT??!!!
How do I get there?
Basically, the underlying space should not be
affected in order to maintain topology.
So, What IS the Condition?!
Simple.
If I were to overlay the two stars, the links must
be the same!
The condition is: Lk a Lk b = Lk ab
Finally,
THANKS!!!
Wake up now!!