close

Вход

Забыли?

вход по аккаунту

?

Short Version[PPT]

код для вставкиСкачать
Overlay Stitch Meshing
5/2/2007
Don Sheehy
Overlay Stitch Meshing
1
A competitive algorithm for
no-large-angle triangulation
Don Sheehy
Joint work with Gary Miller and
Todd Phillips
To appear at ICALP 2007
5/2/2007
Don Sheehy
Overlay Stitch Meshing
2
The Problem
Input: A Planar Straight Line Graph
5/2/2007
Don Sheehy
Overlay Stitch Meshing
3
The Problem
Input: A Planar Straight Line Graph
Output: A Conforming Triangulation
5/2/2007
Don Sheehy
Overlay Stitch Meshing
4
The Problem
Input: A Planar Straight Line Graph
Output: A Conforming Triangulation
5/2/2007
Don Sheehy
Overlay Stitch Meshing
5
Why would you want to do that?
5/2/2007
Don Sheehy
Overlay Stitch Meshing
6
5/2/2007
Don Sheehy
Overlay Stitch Meshing
7
5/2/2007
Don Sheehy
Overlay Stitch Meshing
8
5/2/2007
Don Sheehy
Overlay Stitch Meshing
9
5/2/2007
Don Sheehy
Overlay Stitch Meshing
10
5/2/2007
Don Sheehy
Overlay Stitch Meshing
11
What went wrong?
5/2/2007
Don Sheehy
Overlay Stitch Meshing
12
?
?
What if you don’t know the function?
5/2/2007
Don Sheehy
Overlay Stitch Meshing
13
2 Definitions of Quality
1. No Large Angles [Babuska, Aziz 1976]
5/2/2007
Don Sheehy
Overlay Stitch Meshing
14
2 Definitions of Quality
1. No Large Angles [Babuska, Aziz 1976]
2. No Small Angles
5/2/2007
Don Sheehy
Overlay Stitch Meshing
15
No Small Angles
5/2/2007
Don Sheehy
Overlay Stitch Meshing
16
No Small Angles
You may have heard of these before.
Delaunay Refinement
Sparse Voronoi Refinement
Quadtree
5/2/2007
Don Sheehy
Overlay Stitch Meshing
17
Paying for the spread
Spread = L/s
L
s
5/2/2007
Don Sheehy
Overlay Stitch Meshing
18
Paying for the spread
Optimal No-Large-Angle Triangulation
5/2/2007
Don Sheehy
Overlay Stitch Meshing
19
Paying for the spread
What if we don’t allow small angles?
5/2/2007
Don Sheehy
Overlay Stitch Meshing
20
Paying for the spread
What if we don’t allow small angles?
O(L/s) triangles!
5/2/2007
Don Sheehy
Overlay Stitch Meshing
21
Paying for the spread
What if we don’t allow small angles?
Fact: For inputs with NO edges,
no-small-angle meshing
algorithms produce output with
O(n log L/s) size and angles
between 30o and 120o
O(L/s) triangles!
5/2/2007
Don Sheehy
Overlay Stitch Meshing
22
What to do?
Small input angles can force even smaller ouput
angles. [Shewchuk ’02]
5/2/2007
Don Sheehy
Overlay Stitch Meshing
23
No Large Angles
5/2/2007
Don Sheehy
Overlay Stitch Meshing
24
Polygons with Holes
[Bern, Mitchell, Ruppert 95] –
- All triangles are nonobtuse.
- Output has O(n) triangles.
5/2/2007
Don Sheehy
Overlay Stitch Meshing
25
Polygons with Holes
[Bern, Mitchell, Ruppert 95] –
- All triangles are nonobtuse.
- Output has O(n) triangles.
Does not work for arbitrary PSLGs
5/2/2007
Don Sheehy
Overlay Stitch Meshing
26
Paterson’s Example
Requires пЃ‘(n2) points.
O(n)
points
O(n)
lines
5/2/2007
Don Sheehy
Overlay Stitch Meshing
27
Paterson’s Example
Requires пЃ‘(n2) points.
O(n)
points
O(n)
lines
5/2/2007
Don Sheehy
Overlay Stitch Meshing
28
Paterson’s Example
Requires пЃ‘(n2) points.
O(n)
points
O(n)
lines
5/2/2007
Don Sheehy
Overlay Stitch Meshing
29
Paterson’s Example
Requires пЃ‘(n2) points.
O(n)
points
O(n)
lines
5/2/2007
Don Sheehy
Overlay Stitch Meshing
30
Paterson’s Example
Requires пЃ‘(n2) points.
O(n)
points
O(n)
lines
5/2/2007
Don Sheehy
Overlay Stitch Meshing
31
Paterson’s Example
Requires пЃ‘(n2) points.
O(n)
points
O(n)
lines
5/2/2007
Don Sheehy
Overlay Stitch Meshing
32
Propagating Paths
5/2/2007
Don Sheehy
Overlay Stitch Meshing
33
Propagating Paths
5/2/2007
Don Sheehy
Overlay Stitch Meshing
34
Propagating Paths
First introduced by Mitchell [93]
Later Improved by Tan [96]
Worst Case Optimal Size O(n2)
Angle bounds: 132o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
35
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
36
The OSM Algorithm
(Overlay Stitch Meshing)
Results:
1. Angles bounded by 170o
2. O(log L/s) competitive size
5/2/2007
Don Sheehy
Overlay Stitch Meshing
37
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
38
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
39
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
40
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
41
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
42
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
43
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
44
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
45
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
46
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
47
The OSM Algorithm
(Overlay Stitch Meshing)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
48
The OSM Algorithm
(Overlay Stitch Meshing)
• An Overlay Edge is kept if
1. It does not intersect the input,
OR
2. It forms a good intersection with the input.
at least 30o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
49
Angle Guarantees
5/2/2007
Don Sheehy
Overlay Stitch Meshing
50
Angle Guarantees
5/2/2007
Don Sheehy
Overlay Stitch Meshing
51
Angle Guarantees
We want to show that angles at
stitch vertices are bounded by 170o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
52
Angle Guarantees
An Overlay Triangle
5/2/2007
Don Sheehy
Overlay Stitch Meshing
53
Angle Guarantees
An Overlay Triangle
An Overlay Edge
5/2/2007
Don Sheehy
Overlay Stitch Meshing
54
Angle Guarantees
Gap Ball
An Overlay Triangle
An Overlay Edge
5/2/2007
Don Sheehy
Overlay Stitch Meshing
55
Angle Guarantees
A Good Intersection
5/2/2007
Don Sheehy
Overlay Stitch Meshing
56
Angle Guarantees
A Bad Intersection
5/2/2007
Don Sheehy
Overlay Stitch Meshing
57
Angle Guarantees
A Bad Intersection
5/2/2007
Don Sheehy
Overlay Stitch Meshing
58
Angle Guarantees
How Bad can it be?
A Bad Intersection
5/2/2007
Don Sheehy
Overlay Stitch Meshing
59
Angle Guarantees
How Bad can it be?
About 10o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
About 170o
60
Angle Guarantees
How Bad can it be?
Theorem: If any input edge
makes a good intersection
with an overlay edge then
any other intersection on
that edge is not too bad.
About 10o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
About 170o
61
Size Bounds
5/2/2007
Don Sheehy
Overlay Stitch Meshing
62
Size Bounds
How big is the resulting triangulation?
5/2/2007
Don Sheehy
Overlay Stitch Meshing
63
Size Bounds
How big is the resulting triangulation?
Goal: log(L/s)-competitive with optimal
5/2/2007
Don Sheehy
Overlay Stitch Meshing
64
Local Feature Size
lfs(x) = distance to second nearest input vertex.
lfs(x)
5/2/2007
x
Don Sheehy
Overlay Stitch Meshing
Note: lfs is defined on the
whole plane before we do
any meshing.
65
Ruppert’s Idea
r = пЃ‘(lfs(c))
r
c
пѓћ area(D) = пЃ‘(lfs(c)2)
пѓћ # of triangles = пЃ‘(ss 1/lfs(x,y)2 dxdy)
5/2/2007
Don Sheehy
Overlay Stitch Meshing
66
Ruppert’s Idea
r = пЃ‘(lfs(c))
r
пѓћ area(D) = пЃ‘(lfs(c)2)
c
пѓћ # of triangles = пЃ‘(ss 1/lfs(x,y)2 dxdy)
dx
This represents a
пЃ‘(dxdy/lfs(x,y)2)
fraction of the triangle.
dy
5/2/2007
Don Sheehy
Overlay Stitch Meshing
67
Ruppert’s Idea
r = пЃ‘(lfs(c))
r
c
пѓћ area(D) = пЃ‘(lfs(c)2)
пѓћ # of triangles = пЃ‘(ss lfs(x,y)-2 dxdy)
Caveat: Only Works for meshes
with bounded smallest angle.
5/2/2007
Don Sheehy
Overlay Stitch Meshing
68
Extending Ruppert’s Idea
-2
# of triangles = пЃ‘(ss lfs(x,y) dxdy)
# of triangles along e = пЃ‘(sz2 e lfs(z)-1 dz)
An input edge e intersecting
the overlay mesh
5/2/2007
Don Sheehy
Overlay Stitch Meshing
69
Extending Ruppert’s Idea
-2
# of triangles = пЃ‘(ss lfs(x,y) dxdy)
# of triangles along e = пЃ‘(sz2 e lfs(z)-1 dz)
Now we can compute the size of
our output mesh. We just need
to compute these integrals.
5/2/2007
Don Sheehy
Overlay Stitch Meshing
70
Output Size
-2
Overlay Mesh Size = пЃ‘(ss lfs(x,y) dxdy)
O(n log L/s)
Stitch Vertices Added = пЃ‘(sz2 E lfs(z)-1 dz)
O(log L/s)ВЈ |OPT|
We’ll Prove this now
5/2/2007
Don Sheehy
Overlay Stitch Meshing
71
What can we say about the optimal
no-large-angle triangulation?
5/2/2007
Don Sheehy
Overlay Stitch Meshing
72
Competitive Analysis
Warm-up
90o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
73
Competitive Analysis
Warm-up
?o
5/2/2007
Don Sheehy
Overlay Stitch Meshing
74
Competitive Analysis
Warm-up
5/2/2007
Don Sheehy
Overlay Stitch Meshing
75
Competitive Analysis
Warm-up
5/2/2007
Don Sheehy
Overlay Stitch Meshing
76
Competitive Analysis
Warm-up
Suppose we have a triangulation with all angles at least 170o.
the optimal
5/2/2007
Don Sheehy
Overlay Stitch Meshing
77
Competitive Analysis
Warm-up
Suppose we have a triangulation with all angles at least 170o.
the optimal
5/2/2007
Every input edge is covered
by empty lenses.
Don Sheehy
Overlay Stitch Meshing
78
Competitive Analysis
This is what we have to integrate over.
e’
We show that in each lens, we put
O(log (L/s)) points on the edge.
In other words:
se’ 1/lfs(z) dz = O(log (L/s))
5/2/2007
Don Sheehy
Overlay Stitch Meshing
79
Competitive Analysis
sz2 e’ 1/lfs(z) dz = O(log (L/s))
e’
5/2/2007
Don Sheehy
Overlay Stitch Meshing
80
Competitive Analysis
sz2 e’ 1/lfs(z) dz = O(log (L/s))
t
e’
sz2 e’ 1/lfs(z) dz · 2s0s 1/s + 2ssl/2 1/x dx
Parametrize e’ as [0, l]
1st trick: lfs Вё s everywhere
= O(1) + O(log l/s)
2nd trick: lfs Вё ct for t2 [0,l/2]
5/2/2007
Don Sheehy
Overlay Stitch Meshing
= O(log L/s)
81
Conclusions
5/2/2007
Don Sheehy
Overlay Stitch Meshing
82
Conclusion
• A new algorithm for no-large-angle
triangulation.
• The output has bounded degree triangles.
• The first log-competitive analysis for such
an algorithm.
• We used some of the high school calculus
you thought you forgot.
5/2/2007
Don Sheehy
Overlay Stitch Meshing
83
Where to go from here?
• 3D?
• Better angle bounds?
• Leverage lower bound technology for
constant competitive algorithm.
5/2/2007
Don Sheehy
Overlay Stitch Meshing
84
Thank you.
5/2/2007
Don Sheehy
Overlay Stitch Meshing
85
Документ
Категория
Презентации
Просмотров
1
Размер файла
2 768 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа