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