TU Wien:Algorithmic Geometry VU (Nöllenburg)/Ideas of proofs für die ganzen Lemmas und Theorems

Aus VoWi
Zur Navigation springen Zur Suche springen

Convex Hulls[Bearbeiten | Quelltext bearbeiten]

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


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 .

Line Segment Intersection[Bearbeiten | Quelltext bearbeiten]

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
In order to bring into the form , we view as a planar graph
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 =>

Polygon Triangulation[Bearbeiten | Quelltext bearbeiten]

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

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 ...
  • Initialize sweep-line status ...
  • Handle a single event ...
    • ...
    • Find, remove, add element in ...
    • Add diagonals to ...
  • Space: obviously


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.


Range Searching - Part 1[Bearbeiten | Quelltext bearbeiten]

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:
  • 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 =>
Space:

uses space, need space per layer of .
We have layers => total space is

Time:

  • Initially sort on y-coord =>
  • in each step split sorted list in sorted sublists (left/right of median) =>
  • 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.

Range Searching - Part 2[Bearbeiten | Quelltext bearbeiten]

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
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.

Point Location[Bearbeiten | Quelltext bearbeiten]

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
  • the theorem holds independently of the input set

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

No proof. (or see Chapter 6.4)


Lemma 3: Let be a set of crossing-free segments and .

Then search path in longer than


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.

Voronoi[Bearbeiten | Quelltext bearbeiten]

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
(*)
(**)
insert into:
(*)
(**)


Theorem 3:

  • A point is a Voronoi vertex
  • The bisector defines a Voronoi edge with

Proof:

  • "<=": Let be the point with the property and the 3 points on the boundary
=>
  • "=>": Let be the Voronoi vertex for 3 points
=> for any


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.

Delaunay[Bearbeiten | Quelltext bearbeiten]

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

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
  • bisector defines a Voronoi-edge with


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.

Duality[Bearbeiten | Quelltext bearbeiten]

Lemma 1: The following properties hold

  • and
  • lies below/on/above passes above/through/below
  • and intersect in point passes through and
  • 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 =>
#edges: each line intersects lines => edges per line
#cells: Euler
We need to deal with the unbounded cells => add dummy vertex
=>


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
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


Theorem 3: The arrangement of a set of lines can be constructed in time and space.

Proof:

  • bounding box =
  • intersections:

Quadtrees[Bearbeiten | Quelltext bearbeiten]

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
  • maximal distance of two points in a depth- square is
  • each inner node has at least two points in its corresponding square:
  • 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
=> 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.

WSPD[Bearbeiten | Quelltext bearbeiten]

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

Proof:

  • assume all cells have side length
  • consider hypercube with side length containing
cells of intersect in each dimension at most cells of grid intersect


Theorem 3: Given a point set in and

we can construct an s-WSPD with pairs in time

Sketch of proof:

  • simplifying assumption: no quadtree compression required
in wsPairs(, , , ) sizes of and differ by at most factor
  • 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
  • call non-trivial => and not ws,
  • let be side length of and the radius of the enclosing ball
  • side length of is or and
  • not ws => ball distance


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
knew:
=> using induction hypothesis =>
(*)
(**)
triangle inequality => , where , and
in (*) /* using (**) */
choose:
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
Let be shortest x-y path in
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
set
I have no idea what I'm doing...