Lemma: For a set of points
is a convex polygon that contains
and whose vertices are in
.
Observation:
is an edge of
each point
- strictly right of the oriented line
or
- on the line segment
![{\displaystyle {\overline {pc}}}](/index.php?title=Spezial:MathShowImage&hash=ddcde43ad33aa4602f657a5cdbed88c5&mode=mathml)
Lemma: The convex hull of
points in the plane can be computed in
time.
Theorem 1: The convex hull of
points in the plane can be computed in
time. --> Graham's Scan
Theorem 2: The convex hull
of
points
in
can be computed in
time using Gift Wrapping (also called Jarvis' March), where
.
Theorem 3: The convex hull
of
points
in
can be computed in
time using Chan's Algorithm, where
.
Lemma 1: Algorithm FindIntersections finds all intersection points and the line segments involved.
Proof: Induction on the number of events processed.
Case 1:
is a line segment endpoint =>
has been in the Event-Queue
,
has stored
, furthermore
and
are in the sweep line data structure
. (
is a binary search tree)
Case 2:
ist not a line segment endpoint => Consider why
must be in the event-queue
: Induction on position
where
and
are neighbors on
=> An event
exists when
and
became neighbors =>
handled correctly =>
Lemma 2: Algorithm FindIntersections has running time
, where
is the number of intersection points.
Proof: Changes to
each take
time but at event
we have costs
=> in total, summing all
, we get ![{\displaystyle O(m\log {n})}](/index.php?title=Spezial:MathShowImage&hash=9597e86e692747ff4660abf0b7f70d20&mode=mathml)
In order to bring
into the form
, we view
as a planar graph ![{\displaystyle G=(V,E)}](/index.php?title=Spezial:MathShowImage&hash=c311905eab60237306c75dfad5d0ca29&mode=mathml)
We know that
.
Each face is bounded by >= 3 edges. Each edge bounds at most 2 faces. =>
Use Euler's formula. =>
=> use
=>
Theorem 1: Let
be a set of
line segmens in the plane. Then we can compute all intersections in
and the involved line segments in
time and
space.
Euler's formula (for connected planar graphs):
Proof: Initially: 1 component, 4 faces => delete an edge: remove a face and add a component => end:
components, 1 face =>
Theorem 1: Each simple polygon with
corners admits a triangulation; any such triangulation contains exactly
triangles.
could be guarded by
cameras placed in the
triangles
can be guarded by
cameras placed on the diagonals
can be guarded by even fewer cameras placed on the corners
Theorem 2: For a simple polyon with
vertices,
cameras are sometimes necessary and always sufficient to guard it.
Proof: Find a simple polygon with
corners that requires
cameras! (Das mit den Zacken nach oben, zwischen denen immer ein wenig Abstand ist)
Conclusion: Given a triangulation, the
cameras that guard the polygon can be placed in
time.
Lemma 1: A polygon is y-monotone if it has no split vertices or merge vertices.
Proof: Assume
is not y-monotone
Start with 2 vertices
and
which are part of the polygon
and lie on the sweep line
- i.e. let
be the leftmost intersection of
with
.
From
, walk along the polygon-border with interior to the left until hitting
again in a point ![{\displaystyle r}](/index.php?title=Spezial:MathShowImage&hash=4b43b0aee35624cd95b910189b3dc231&mode=mathml)
- if
, then there is a split vertex.
- if
, walk from
along the polygon-border with interior to the right until hitting
in point
- => on that path there is a merge vertex.
Lemma 2: Algorithm MakeMonotone computes a set of crossing-free diagonals of
, which partition
into y-monotone polygons.
Theorem 3: A simple polygon with
vertices can be partitioned into y-monotone polygons in
time and
space.
- Construct priority queue
... ![{\displaystyle O(n)}](/index.php?title=Spezial:MathShowImage&hash=7ba55e7c64a9405a0b39a1107e90ca94&mode=mathml)
- Initialize sweep-line status
... ![{\displaystyle O(1)}](/index.php?title=Spezial:MathShowImage&hash=5e079a28737d5dd019a3b8f6133ee55e&mode=mathml)
- Handle a single event ...
... ![{\displaystyle O(\log {n})}](/index.php?title=Spezial:MathShowImage&hash=293089b84708ceec3debafb55e35eebf&mode=mathml)
- Find, remove, add element in
... ![{\displaystyle O(\log {n})}](/index.php?title=Spezial:MathShowImage&hash=293089b84708ceec3debafb55e35eebf&mode=mathml)
- Add
diagonals to
... ![{\displaystyle O(1)}](/index.php?title=Spezial:MathShowImage&hash=5e079a28737d5dd019a3b8f6133ee55e&mode=mathml)
- Space: obviously
![{\displaystyle O(n)}](/index.php?title=Spezial:MathShowImage&hash=7ba55e7c64a9405a0b39a1107e90ca94&mode=mathml)
Theorem 4: A y-monotone polygon with
vertices can be triangulated in
time.
Theorem 5: A simple polygon with
vertices can be triangulated in
time and
space.
Theorem 1: A set of
points in
can be preprocessed in
time and
space so that we can answer range queries in
time, where
is te number of reported points.
Lemma 1: A
-tree for
points in
can be constructed in
time, using
space.
Proof sketch:
- Determine median:
- make two lists sorted on x- and y-coordinates
- at each step, determine median an divide the lists
- We get the following recurrence:
![{\displaystyle T(n)={\begin{cases}O(1))&n=1\\O(n)+2T(\left\lceil {\frac {n}{2}}\right\rceil )&otherwise\end{cases}}}](/index.php?title=Spezial:MathShowImage&hash=ae0a56c6ade5cb34b4ba8052e7bb6450&mode=mathml)
- solves to
(analogous to MergeSort)
- linear space, since we are using a binary tree with
leaves
Lemma 2: A range query with an axis-aligned rectangle
in a
-tree on
points takes
time, where
is the number of reported points
Proof sketch:
- Calls to ReportSubtree take
time in total
- Still missing: number of remaining nodes visited, determine a suitable recurrence and use Master Theorem TODO: TBD
Lemma 3: A Range Tree for
points in
uses
space and can be constructed in
time.
Proof: Creation of
:
, creation of
:
for each internal node of
=> ![{\displaystyle O(n^{2}\log {n})}](/index.php?title=Spezial:MathShowImage&hash=f9fb9953ced1baf6fd60f5d0ab823500&mode=mathml)
Space:
uses
space,
need
space per layer of
.
- We have
layers => total space is ![{\displaystyle O(n\log {n})}](/index.php?title=Spezial:MathShowImage&hash=e2357327a56e2af6536c18de1747e21c&mode=mathml)
Time:
- Initially sort
on y-coord => ![{\displaystyle O(n\log {n})}](/index.php?title=Spezial:MathShowImage&hash=e2357327a56e2af6536c18de1747e21c&mode=mathml)
- in each step split sorted list in sorted sublists (left/right of median) =>
![{\displaystyle O(n)}](/index.php?title=Spezial:MathShowImage&hash=7ba55e7c64a9405a0b39a1107e90ca94&mode=mathml)
- We have
layers =>
in total.
Lemma 4: A range query in a Range Tree takes
time, where
is the number of reported points.
Proof sketch: In each visited node:
1D Range Query, which takes
time.
, where
is the number of visited nodes
Theorem 2: A Layered Range Tree on
pints in
can be constructed in
time and space. Range queries take
time, where
is the number of reported points.
Lemma 1: An interval tree for
intervals needs
space and has depth
. It can be constructed in time
Lemma 2: Using an interval tree we can find all
intervals containing a query point
in
time.
Theorem 1: Let
be a set of horizontal (axis-parallel) line segments in the plane. All
line segments that intersect a vertical query segment (an axis-parallel rectangle
) can be found in
time. The data structure requires
space and construction time.
Proof:
- case 1: all collinear
- case 2: Geometric proof where 2 lines between the neighboring areas
-->
-->
intersect. Assume the contrary and somewhen during the proof,
will be nearer to
(instead of to
) and this is a contradiction.
- case 3: Also some contradiction... ~ assume contrary => voronoi diagram
must be connected, i.e. no full lines => contradiction
Lemma 3: A segment tree for
intervals requires
space and can be constructed in
time
Sketch of proof:
- InsertSegmentTree(
)
- if
then
- store
in ![{\displaystyle I(v)}](/index.php?title=Spezial:MathShowImage&hash=2045fac6dfd26e6847d378cfcc725653&mode=mathml)
- else
- if
then
- InsertSegmentTree(
)
- if
then
- InsertSegmentTree(
)
Lemma 4: All
intervals that contain a query point
can be computed in
time using a segment tree.
Theorem 2: Let
be a set of interior-disjoint line segments in the plane. All
segments that intersect a vertical query segment (an axis-parallel query rectangle
) can be found in time
. The corresponding data structure uses
space and
construction time.
Lemma 1: The trapezoidal map
of a set
of
segments in general position contains at most
vertices and at most
trapezoids.
Theorem 1: The algorithm computes the trapezoidal map
and the search structure
for a set
of
segments in expected
is
and the expected query time is
.
Observations:
- worst case: size of
is quadratic and query time is linear
- hope: that happens rarely!
- consider expected time and size over all
permutations of ![{\displaystyle S}](/index.php?title=Spezial:MathShowImage&hash=5dbc98dcc983a70728bd082d1a47546e&mode=mathml)
- the theorem holds independently of the input set
![{\displaystyle S}](/index.php?title=Spezial:MathShowImage&hash=5dbc98dcc983a70728bd082d1a47546e&mode=mathml)
Proof:
- define random variables and consider their expected values
- perform backward analysis
- --> details on blackboard TODO: TBD!
Lemma 2: Let
be a set of
crossing-free segments, let
be a query point and let
.
- Then
search path for
longer than ![{\displaystyle 3\lambda \ln {n+1}]\leq {\frac {1}{(n+1)^{\lambda \ln {1.25-1}}}}}](/index.php?title=Spezial:MathShowImage&hash=455f76f1347c4c8939d51696465b1cd1&mode=mathml)
No proof. (or see Chapter 6.4)
Lemma 3: Let
be a set of
crossing-free segments and
.
- Then
search path in
longer than ![{\displaystyle 3\lambda \ln {n+1}]\leq {\frac {2}{(n+1)^{\lambda \ln {1.25-3}}}}}](/index.php?title=Spezial:MathShowImage&hash=bea22dc014401cc0cf57cf235b7fc3b5&mode=mathml)
Theorem 2: Let
be a subdivision of the plane with
edges.
- There is a search structure for point location within
that has
space and
query time.
Theorem 1: Let
be a set of
points. If all points are collinear, then
consists of
parallel lines.
- Otherwise
is connected and its edges are either segments or half lines.
Theorem 2: Let
be a set of
points. Then
has at most
nodes and
edges.
Proof: It's almost a planar graph => add a dummy vertex and apply Euler's formula.
- case non-collinear:
almost planar graph
, where
(*)
(**)
![{\displaystyle 2|E|=\sum _{v\in V}deg(v)+deg(v_{d})\geq 3(|V|+1)}](/index.php?title=Spezial:MathShowImage&hash=3a9597842d3cb77b0ad53323d30736cc&mode=mathml)
- insert into:
- (*)
![{\displaystyle 2(|V|-1+n)\geq 3|V|+3}](/index.php?title=Spezial:MathShowImage&hash=4c3e87d2019ed7fc611403819bc912b1&mode=mathml)
- (**)
![{\displaystyle 2|E|\geq 3(|E|-n+2)\Leftrightarrow |E|\leq 3n-6}](/index.php?title=Spezial:MathShowImage&hash=62ae30cdc11f3fadd55fe1a1f539b063&mode=mathml)
Theorem 3:
- A point
is a Voronoi vertex ![{\displaystyle \Leftrightarrow |\delta C_{P}(q)\cap P|\geq 3}](/index.php?title=Spezial:MathShowImage&hash=c3b283a348066f1a70b657ea0045a855&mode=mathml)
- The bisector
defines a Voronoi edge
with ![{\displaystyle \delta C_{P}(q)\cap P=(p_{i},p_{j})}](/index.php?title=Spezial:MathShowImage&hash=ace3964c468e7d0bd4746a56776f209c&mode=mathml)
Proof:
- "<=": Let
be the point with the property and
the 3 points on the boundary
- =>
![{\displaystyle q\in \delta V(p)\cap \delta V(p')\cap \delta V(p'')}](/index.php?title=Spezial:MathShowImage&hash=aab7acbdb0a6c659ff8d4c3d85922371&mode=mathml)
- "=>": Let
be the Voronoi vertex for 3 points ![{\displaystyle p,p',p''}](/index.php?title=Spezial:MathShowImage&hash=5a0c26a8891a62540ecf4c3f1035c73e&mode=mathml)
- =>
for any ![{\displaystyle x\in P}](/index.php?title=Spezial:MathShowImage&hash=6a89bdeb2629596c7fe68fdcb483a668&mode=mathml)
Lemma 1: New arcs on
arise only from point events.
Proof: Assume contrary: assume that parabula
enters
.
- case 1: =>
=> Contradiction (?)
- case 2: Move
some
down and let circle stick to
and go through
=> Cannot construct a circle which goes through
,
and
and touches
anymore => geometrically impossible.
Collorary:
consists of at most
parabolic arcs.
Lemma 2: Arcs of
disappear exactly at circle event
Proof: Let
be a disappearing arc... => probably also with the geometrically impossible circle?
Lemma 3: For each Voronoi vertex there is a circle event.
Theorem 4: For a set
of
points, Fortune's sweep algorithm computes the Voronoi Diagram
in
time and
space.
Proof sketch:
- Each event requires
time
point events
circle events (= #vertices of
)
- False alarms are deleted from
before they are processed.
Theorem 1: Let
be a set of
points, not all collinear. Let
be the number of points of
.
- Then every triangulation of
has
triangles and
edges.
- => Compute
and
! =>
- Then every triangulation of
has
triangles and
edges.
Theorem 2 (Thales' Theorem): All triangles formed by the end points
of the diameter of a circle
and a third point on
are rigth triangles.
Theorem 2': Let
be a circle,
a line intersecting
in points
and
, and
points on the same side of
.
- Suppose that
and
lie on
,
lies inside
and
lies outside
.
- Then
![{\displaystyle \angle {aeb}<\angle {acb}=\angle {ac'b}<\angle {adb}}](/index.php?title=Spezial:MathShowImage&hash=8382ba85e51c9b56b180deba2fe741e7&mode=mathml)
Sketch of proof: geometric, see slide #7
Lemma 1: Let
and
be two triangles in
and let
be the circumcirle of
.
- Then
is illegal iff
.
- If
form a convex quadrilateral s.t.
then exactly one of
and
is an illegal edge.
Theorem 3:
is crossing-free.
Sketch of proof:
- The bisector
defines a Voronoi-edge
with
(*)
- or
- The edge
is in
there is an empty circle
with
and
on the boundary. (**)
(*) Theorem about Voronoi-Diagrams:
- point
is a Voronoi-vertex ![{\displaystyle \Leftrightarrow \left|C_{p}(q)\cap P\right|\geq 3}](/index.php?title=Spezial:MathShowImage&hash=3546ce9bc9ac13a54d0911c94e4aea60&mode=mathml)
- bisector
defines a Voronoi-edge
with ![{\displaystyle C_{p}(q)\in P=\{p_{i},p_{j}\}}](/index.php?title=Spezial:MathShowImage&hash=f25cb9441669c6a73a1eb710b13a1a5a&mode=mathml)
Theorem 4: Let
be a set of points.
- Points
are vertices of the same face of
circle through
is empty
- Edge
is in
there is an empty circle
through
and
.
Theorem 5: Let
be a set of points in
and let
be a triangulation of
.
is a Delaunay-Triangulation
circumcircle of each triangle has empty interior.
Sketch of proof:
- "<=": clear
- "=>": use Lemma 1
Theorem 6: Let
be a set of points and
a triangulation of
.
is legal
is a Delaunay-Triangulation.
Obs: If
is in general position
is unique => legal triangulation is unique
- We know that:
is angle-optimal =>
is legal =>
is angle-optimal!
- If
is not in general position, then at least for any triangulation of a "large" face of
the minimum angles are equal.
Theorem 7: For any
points in
a Delaunay-triangulation can be computed in
time.
- (Voronoi-Diag. + Triangulation of "big" faces)
Corollary: For
points in general position an angle-optimal triangulation can be computed in
time. If the points are not in general position, a triangulation with maximum smallest angle can be computed in the same
time.
Lemma 1: The following properties hold
and ![{\displaystyle (l^{*})^{*}=l}](/index.php?title=Spezial:MathShowImage&hash=26a92bdcb0888fae26912f58662c3182&mode=mathml)
lies below/on/above
passes above/through/below ![{\displaystyle l*}](/index.php?title=Spezial:MathShowImage&hash=218cb0bdbcd91019e9bc15a7b182585a&mode=mathml)
and
intersect in point
passes through
and ![{\displaystyle l_{2}^{*}}](/index.php?title=Spezial:MathShowImage&hash=ecd92726b80b2bdb305ea2e2678778b3&mode=mathml)
collinear
intersect in a common point
Theorem 1: Let
be a simple line arrangement for
lines. Then
has
vertices,
edges, and
cells.
Proof:
- #vertices: each pair of lines defines one vertex =>
![{\displaystyle {\binom {n}{2}}}](/index.php?title=Spezial:MathShowImage&hash=4e08c776b6e778b44ea81c63304f6966&mode=mathml)
- #edges: each line intersects
lines =>
edges per line
- #cells: Euler
- We need to deal with the unbounded cells => add dummy vertex
![{\displaystyle |V|+1}](/index.php?title=Spezial:MathShowImage&hash=0c9b3865f5c46f01e45299bb04c31f9d&mode=mathml)
- =>
![{\displaystyle |F|=|E|-|V|+1=n^{2}-{\binom {n}{2}}+1}](/index.php?title=Spezial:MathShowImage&hash=34a1dbb17f22cff00d7ce5b840decfe0&mode=mathml)
![{\displaystyle =n^{2}-{\frac {n^{2}-n}{2}}+1={\frac {n^{2}}{2}}-{\frac {n}{2}}+n+1={\binom {n}{2}}+n+1}](/index.php?title=Spezial:MathShowImage&hash=db25ba6656471c4eb59d69245f8aa97f&mode=mathml)
Theorem 2: For an arrangement
of
lines in the plane and a line
the zone
consists of at most
edges.
Proof: Assume
is horizontal; define left/right bounding edges.
- We show: #left bounding edges
![{\displaystyle \leq 3n}](/index.php?title=Spezial:MathShowImage&hash=6460deb39d31dd5f3d3d68bdae04ef40&mode=mathml)
- use induction:
: obviously holds
: Let
be rightmost line in
intersecting
- * for
we have
left bounding edges
- *
intersects two edges of rightmost cell, splits them and adds one left bounding edge for ![{\displaystyle l_{1}}](/index.php?title=Spezial:MathShowImage&hash=e2764e31056bd03a8372f87d4927a134&mode=mathml)
Theorem 3: The arrangement
of a set of
lines can be constructed in
time and space.
Proof:
- bounding box =
![{\displaystyle O(n^{2})}](/index.php?title=Spezial:MathShowImage&hash=9f84a66d88d24c3b1bc91df5b5346a13&mode=mathml)
- intersections:
![{\displaystyle \sum _{i=1}^{n}O(i)\Rightarrow O(n^{2})}](/index.php?title=Spezial:MathShowImage&hash=549bed2cd4142d2d12c79f90e29caae6&mode=mathml)
Lemma 1: The depth of
is at most
where
is the smallest distance in
and
is the side length of the root square
Proof:
- at each step down in
the square side length halves
side length at depth
is ![{\displaystyle {\frac {s}{2^{i}}}}](/index.php?title=Spezial:MathShowImage&hash=cec8b650a9342498500838bcf0f59eff&mode=mathml)
- maximal distance of two points in a depth-
square is ![{\displaystyle {\frac {s{\sqrt {2}}}{2^{i}}}}](/index.php?title=Spezial:MathShowImage&hash=7cba1f90f3e618b59308b029782ec3c2&mode=mathml)
- each inner node has at least two points in its corresponding square:
![{\displaystyle {\frac {s{\sqrt {2}}}{2^{i}}}\geq c\Leftrightarrow 2^{i}\leq {\frac {s{\sqrt {2}}}{c}}\Leftrightarrow i\leq \log {\frac {s}{c}}+{\frac {1}{2}}}](/index.php?title=Spezial:MathShowImage&hash=3a12759d7bc7218f68fb4235ec19e06b&mode=mathml)
- one more level for the leaves
Theorem 1: A quadtree
on
points with depth
has
nodes and can be constructed in
time.
Proof:
- each inner node has four children => #leaves = 3 #inner-nodes + 1
- each inner node contains
point,
- squares at one level partition
![{\displaystyle Q}](/index.php?title=Spezial:MathShowImage&hash=f09564c9ca56850d4cd6b3319e541aee&mode=mathml)
- => at most
inner nodes per level and
nodes in total
- distribute
points per level to all children =>
time per level
Theorem 2: Let
be a quadtree with depth
. The neighbor of a node
in any direction can be found in
time.
Proof: each recursive step takes
time.
Theorem 3: Let
be a quadtree with
nodes and depth
.
- The balanced version
of
has
nodes and can be constructed in
time.
Theorem 4: For a set
of disjoint, octilinear, integer-coordinate polygons with total perimeter
in a square
we can compute in
time a valid adaptive triangular mesh with
triangles.
Lemma 1: see Quadtrees Lemma 1
Theorem 1: see Quadtrees Theorem 1
Theorem 2: A compressed quadtree for
points in
with a fixed dimension
can be constructed in
time.
Lemma 2: Let
be a ball with radius
in
and let
be a set of pairwise disjoint quadtree cells with side length
that intersect
.
- Then it holds
![{\displaystyle |X|\leq (1+\left\lceil {\frac {2r}{x}}\right\rceil )^{d}}](/index.php?title=Spezial:MathShowImage&hash=465c5c35b62fbe6989d1c7b308121418&mode=mathml)
Proof:
- assume all cells have side length
![{\displaystyle x}](/index.php?title=Spezial:MathShowImage&hash=9dd4e461268c8034f5c8564e155c67a6&mode=mathml)
- consider hypercube
with side length
containing ![{\displaystyle K}](/index.php?title=Spezial:MathShowImage&hash=a5f3c6a11b03839d46af9fb43c97c188&mode=mathml)
cells of
intersect
in each dimension at most
cells of grid intersect ![{\displaystyle H}](/index.php?title=Spezial:MathShowImage&hash=c1d9f50f86825a1a2302ec2449c17196&mode=mathml)
Theorem 3: Given a point set
in
and
- we can construct an s-WSPD with
pairs in time ![{\displaystyle O(n\log {n}+s^{d}n)}](/index.php?title=Spezial:MathShowImage&hash=3e8c855f87b6767dd166f4af86053463&mode=mathml)
Sketch of proof:
- simplifying assumption: no quadtree compression required
in wsPairs(
,
,
,
) sizes of
and
differ by at most factor ![{\displaystyle 2}](/index.php?title=Spezial:MathShowImage&hash=c81e728d9d4c2f636f067f89cc14862c&mode=mathml)
- goal: count calls to wsPairs
- call is trivial if it produces no further recursive calls
- each trivial call produces at most one ws pair
- each non-trivial call produces
trivial calls and thus
ws pairs
- let's count non-trivial calls and charge cost to the smaller of the two cells
- goal: each quadtree node has cost
![{\displaystyle O(s^{d})}](/index.php?title=Spezial:MathShowImage&hash=3231d78055dc006ba7864fd5fcd20f39&mode=mathml)
- call non-trivial =>
and
not ws, ![{\displaystyle u\geq v}](/index.php?title=Spezial:MathShowImage&hash=2094dfc9f4f7ce33217f21a4f6c48d2e&mode=mathml)
- let
be side length of
and
the radius of the enclosing ball
- side length of
is
or
and ![{\displaystyle r_{u}\leq 2r_{v}}](/index.php?title=Spezial:MathShowImage&hash=524a537bbe62daf3d94c77739a79ad4b&mode=mathml)
not ws => ball distance ![{\displaystyle \leq s\max {(r_{u},r_{v})}\leq 2sr_{v}=sx{\sqrt {d}}}](/index.php?title=Spezial:MathShowImage&hash=3f9f765e5e927470878d527bbbb4d645&mode=mathml)
Lemma 3: If
is a s-WSPD for suitable
, then
is a t-spanner for
with
edges
Proof: show for all
- use induction on k = #edges on shortest x-y-path
- k = 1
- k > 1:
- let
be in ws-pair
with rep
, rep![{\displaystyle (P_{v})=v}](/index.php?title=Spezial:MathShowImage&hash=745c5cf8bd99eac09359c067e7c0d398&mode=mathml)
- knew:
![{\displaystyle \delta _{G}(x,y)\leq \delta _{G}(x,u)+||uv||+\delta _{G}(v,y)}](/index.php?title=Spezial:MathShowImage&hash=a29c9cd5796aecca7bdbc48e28b486e3&mode=mathml)
- => using induction hypothesis =>
(*)
(**)
- triangle inequality =>
, where
, and
![{\displaystyle \leq 4r+||xy||}](/index.php?title=Spezial:MathShowImage&hash=e7f0780eb11253599d0601b2fc8c1495&mode=mathml)
- in (*)
/* using (**) */
- choose:
![{\displaystyle \Rightarrow }](/index.php?title=Spezial:MathShowImage&hash=67e809ba0431c0bf50d5fcc41f15f26b&mode=mathml)
![{\displaystyle \delta _{G}(x,y)\leq t*||xy||}](/index.php?title=Spezial:MathShowImage&hash=92bbf08fd8f4970f4b622dc1484cda5f&mode=mathml)
- I have no idea what I'm doing...
Theorem 4: For a set
of
points in
and some
we can compute an
-spanner for
with
edges in
time.
Proof: see slides
Theorem 5: The MST obtained from a
-spanner of
is a
-approximation of the EMST of
.
Proof: Let
be an EMST with weight
, let
be a
-spanner.
- For any
![{\displaystyle \{x,y\}\in T}](/index.php?title=Spezial:MathShowImage&hash=674da6dfdae353ce453fe42000a119f0&mode=mathml)
![{\displaystyle ||xy||\leq \delta _{G}(x,y)\leq (1+\varepsilon )||x+y||}](/index.php?title=Spezial:MathShowImage&hash=0fc621155f602e533fa5c7bf2b871b50&mode=mathml)
- Let
be shortest x-y path in ![{\displaystyle G}](/index.php?title=Spezial:MathShowImage&hash=dfcf28d0734569a6a693bc8194de62bf&mode=mathml)
![{\displaystyle G':=\bigcup _{\{x,y\}\in T}\Pi _{g}(x,y)}](/index.php?title=Spezial:MathShowImage&hash=8363c0743a3adc6d3ab6c18505ea0c83&mode=mathml)
![{\displaystyle w(G')\leq \sum _{e\in T}w(\Pi _{G}(e))\leq (1+\varepsilon )\sum _{e\in T}||e||=(1+\varepsilon )w(T)}](/index.php?title=Spezial:MathShowImage&hash=62eb20add5024a6087ab4b566913a3c1&mode=mathml)
![{\displaystyle w(MST(G))\leq w(MST(G'))\leq w(G')\leq (1+\varepsilon )w(T)}](/index.php?title=Spezial:MathShowImage&hash=7fc7c308e6f7bf5b084fcdb1810278d4&mode=mathml)
- I have no idea what I'm doing...
Theorem 6: The diameter obtained from an s-WSPD of
, for
is a
-approximation of the diameter of
.
Proof: Let
be a diameter pair and
is ws pair
, where
, and ![{\displaystyle ||uy||\leq 2r}](/index.php?title=Spezial:MathShowImage&hash=13682ac3a584880338fd1ff7f755c583&mode=mathml)
![{\displaystyle ||uv||\geq r\Leftrightarrow r\leq {\frac {||uv||}{s}}}](/index.php?title=Spezial:MathShowImage&hash=510446951e80836e884b2bed28c2c748&mode=mathml)
![{\displaystyle \Rightarrow ||xy||\leq {\frac {4||uv||}{s}}+||uv||=(1+{\frac {4}{s}})||uv||}](/index.php?title=Spezial:MathShowImage&hash=8b776ac21d372934e6993fc56deb3b19&mode=mathml)
![{\displaystyle ||uv||\leq ||xy||}](/index.php?title=Spezial:MathShowImage&hash=08c31eb04f0cbb352ce2e6aeede8a69e&mode=mathml)
- set
![{\displaystyle s={\frac {4}{\varepsilon }}\Rightarrow ||uv||\geq {\frac {||xy||}{1+\varepsilon }}}](/index.php?title=Spezial:MathShowImage&hash=bf3c658f8eb7a3c99be03f202cc30405&mode=mathml)
- I have no idea what I'm doing...