Geometry combinatorics and algorithms
Prüfungsfragen
Prüfungsfragen
How can one construct an arrangement of lines in R2? Describe the incremental algorithm and prove that its time complexity is quadratic in the number of lines (incl. statement and proof of the Zone Theorem).
Graph in DCEL: insert new line li: start on left of bounding box: find leftmost face, that intersects l. Split face and update everything accordingly. add a vertex at intersection with the next line, continue in that fashion until rightmost face is reached.
Only faces that intersect li are relevant. So called zone: set of cells that intersect li. Thm: there are <10n lines in all cells of L. proof. Assume li is horizontal (else rotate everything) We only consider left bounding faces and show <5n: consider the rightmost intersection point p, where r in L intersects something. R is rightmost cell of L without r. We want to consider what happens, when inserting r: It intersects R at most at 2 points, splitting 2 left bound edges and maybe being left bounding itself. So by induction 5(n-1)+3<5n leftbounding edges. If multiple edges intersect at the same point p, they can additionally split rs edges, so we get 5 new leftbound edges.
How can one test whether there are three collinear points in a set of n given points in R2? Describe an O(n2) time algorithm.
Dualize: (a,b) is a line y:ax-b 3 points are colinear iff the 3 corr. lines intersect. (compute intersection of two lines and store in a hash table, if already there, return true, else false)
How can one compute the minimum area triangle spanned by three out of n given points in R2? Describe an O(n2) time algorithm.
fix two points pq. Then equivalent to finding r closest to line through p and q. Dualize: find closest point l* to p* intersect q* that has the same x-coord and lies on some r*. Then r is the solution. Do this for every pair, incrementally update when inserting new lines then no additional costs.
What is a ham sandwich cut? Does it always exist? How to compute it? State and prove the theorem about the existence of a ham sandwich cut in R2 and describe an O(n2) algorithm to compute it and sketch the O(n log n) algorithm by Edelsbrunner and Waupotitsch.
Line splitting two distinct sets at the same time, such that each side of the line has half of each set. Always exists. proof (and O(n^2) algo): Dualize the points. Then consider the median-level line of both (consisits of line segments and all slopes are distinct so they intersect in at least one point) This point corresponds to a line seperating both sets. O(nlogn): recursive algo, input: (L1,L2,k1,k2,(x1,x2)) With two sets of lines, two k-levels and interval. take mu at line with median slope, seperate plane into 4 quarter by line parallel to mu and one line x=j where j ist the median x-coordinate of all intersection points. If j is in the interval, we can update the interval to (x1,j) or (j,x2) and also dircard one quater of the lines, where the intersection points lie in the resp quater (We pair a big slope with a small slope line)
What is the endpoint visibility graph for a set of disjoint line segments in the plane and how can it be constructed? Give the definition and explain the relation to shortest paths. Describe the O(n2) algorithm by Welzl, including a proof of Theorem 9.14.
Given n disjoint line segments, we connect p and q if they are on the same segment or if pq intersect with the whole set is {p,q} (they see each other)
Constructing: Sweep from vertically down to vertically up.We only need to consider directions parallel to some pq . for p store s(p) segment p sees. if slope of pq is parallel to current direction an s(p) =pq add edge pg. If q is obscured by s(p) no change, if q endpoint of s(p) add pq and s(p):=s(q) if q is endpoint of s that now obscures s(p) change s(p) to s and add pq. We have n^2 events and need sorting thus n^2 log n, to get rid of logn: pq has larger slope than pr iff p* intersect q* has greater x coord than p* intersect r*, can be sorted in linear time usng breast first search
Is there a subquadratic algorithm for General Position? Explain the term 3-Sum hard and its implications and give the reduction from 3-Sum to General Position.
No subquadratic algo, it is known, that quadratic time is required for 3-sum problem. General position: No 3 points colinear: Is equivalent to: are there three points such that their sum is 0? : lift all points tp (p,p^3) 3 of them a,a^3 b,b^3 c,c^3 are colinear iff slope through any pair (a,b),(b,c) is the same iff a+b+c=0
Which problems are known to be 3-Sum-hard? List at least three problems (other than 3-Sum) and briefly sketch the corresponding reductions.
colinearity, minimum area triangle (gen. of general position), GeomBase: given points on lines y=0,y=1,y=2 is there a line passing through 3 of them? 3 sum with distinct points
Algo: sort numbers, i=1,..n j=i+1,k=n, j++ if <0 k++ if >0
What is an (n,s) Davenport-Schinzel sequence and how does it relate to the lower envelope of real-valued continuous functions? Give the precise definitions and some examples. Explain in particular how to apply the machinery to line segments.
sequence of alphabet with n elements, such that so s+2 alternating subsequence. every such sequence can be modeled by lower envelope sequence for n continuous functions. If these functions are line segments, we have 0 in the sequence if no segment is defined here.
What is the value of λs(n), for 1 ⩽ s ⩽ 3? Derive the precise value for s ∈ {1, 2} and prove an O(n log n) upper bound for λ3(n).
1: no seqeunce aba (happens as soon as an element appears twice. 2nd 2n-1. 3: ababab: consider element with least appearances a: a...bab...a can not appear_> del as plus at most 2 more and apply indcution
What is the combinatorial complexity of the lower envelope of a set of n lines/parabolas/line segments?
lines can intersect at most once: n^2 changes. paraboles: one containes in another: 2 changes per pair of line. Line segments: endpoints (4) plus intersection =5
What is a face of a polytope? What is a vertex, an edge, a ridge, a facet?
Give precise definitions!
Face of polytope: Polytope intersected with supporting hyperplane (there is a hyperplane s.t. the face is in hyperplane and P in h+) , dim=k: k-face: vertices: o-faces, edges 1-faces facets: n-1-faces, ridges n-2-faces.
Can you characterize vertex-edge graphs of 3-dimensional polytopes? Explain Steinitz’ Theorem.
3 dim polytope iff 3-connected planar graph
What is a hypercube? What is a simplex? Define these polytope and explain what their faces are.
hypercube: -1<=xi<=1. vertices: some 1 some -1. Simplex convex hull of n affinely independent vertices. Faces: lower dimensional hypercubes/simplices
How many k-faces can a d-dimensional polytope with n vertices have? Prove a nontrivial upper bound.
n over k+1, since every face is a polytope itself.
How connected is the graph of a polytope? State and prove Balinski’s theorem.
d dimensional polytope is d connected. prove: fix some set S of size d-1 and fix some v0. Consider hyperplane through S and v0. Then points are either above ans thus connected to max face or below and connected to min face, v0 connects both, max/min faces are polytopes themselves, so by induction connected
How many facets can a 4-dimensional polytope with n vertices have? Prove a lower bound of Ω(n2).
consider 2 skew symmetric lines, perturb points on in slightly, then ever pair of two adjacent points of each line is delaauney and thus facet.
What is a regular triangulation? Give the definition and show that not all triangulations are regular.
Triangulation regular if it can be obtained by projecting the lower convex hull of a lifting of P to r d+1. Non-regular: 2 triangles in each other.
What is the secondary polytope? Describe the construction and explain its connection to the flip graph of regular triangulations.
secondary polytope: convex hull of GKZ vectors of all triangulations. vertices one to one to regular triangulations, edges are flips. so 1-skeleton is flip graph of regulat triangulations. a flip takes a triangulated convex d+2 dim subset of P and replaces it by unique other triangulation.
Let P ⊂ R2 be a set of n points in general position (with the origin).
What does sum_i=0^n−3 2^i h_i count?
number of embracing set (every embr. set contains triangle and points below)
Show that a simplicial d-dimensional polytope P with d + 2 vertices
has always k(d+2−k) facets, for some 2⩽k⩽d.
dualize: polytope in d+2-d-1=1 dimension: line. Then an embracing set (=facet in primal) is a set that contains a point from the left and one from the right of 0. Assume k points on the left. Then d+2-k on the right. k can not be one, sinceotherwise d+1 vertices are on one side and we thus have d+1 facets on d+2 points which is not possible.
Show that the union of countably many open sets in Rd is open. Show that the union of a finite number of closed sets in Rd is closed. (For the curious reader: These are two of the axioms of an abstract topology. So here we show that the Euclidean space is a topology.) What follows for intersections of open and closed sets? Finally, show that the union of countably many closed sets in Rd is not necessarily closed.
countable union open: \(x\in U=\bigcup_{a=1}^{\infty} \implies x\in U_a \implies \exists \varepsilon: B_{\varepsilon}(x)\subset U_a\subset U.\)
finite union closed: \(F^c=(\bigcup_{i=1}^nF_i)^c=\bigcap_{i=1}^nF_i^c\) by DeMorgan, but only works for finitely many.
finite intersections of open sets are open, countable intersections of closed sets are closed.
counterexample non-closed: \(\bigcup_{n=1}^{\infty}[\frac{1}{n},1]\)
Show that for any P ⊆ Rd the interior P◦ is open, and the closure
\(\bar{P}\) is closed. (Why is there something to show to begin with?)
interior: All points interior to P. let \(x\in P\) then by definition x is interior to P,i.e. \(\exists B_{\varepsilon}(x)\subset P.\)
closure: all points that are neither interior to P nor to \(\mathbb{R}^n\backslash P.\) Let \(x\in \mathbb{R}^n\backslash\bar{P}. \) Then is must be interior to Rn, since otherwise it would be in the boundary or in P.
Prove:
The average vertex degree in a simple planar graph is less than six.
average degree: \(\frac{2|E|}{n}\leq\frac{2(3n-6)}{n}\leq\frac{6n}{n}=6\) (All edges incident to two vertices, average= total/number of vertices)
Show that neither K5 (the complete graph on five vertices) nor K3,3 (the complete bipartite graph where both classes have three vertices) is planar.
K5: number of edges =10, but 3n-6=15-6=9 which is smaller than 10.
K3,3: n=6, e=9 and by euler f=5. Because bipartite, no triangles, hence every face must be bounded by at least 4 edges. and thus 4f<=3e
Let P be a set of n ⩾ 3 points in the plane such that the distance between every pair of points is at least one. Show that there are at most 3n − 6 pairs of points in P at distance exactly one.
Construct graph, s.t. \(uv\in E \iff d(u,v)=1\) then this is planar: if not, an edge ab crossed another edge cd but then some edge in {ac,ad,bc,bd} must have distance less than 1.
A graph is 1-planar if it admits a drawing in the plane in which every edge has at most one crossing. Prove or disprove: The family of 1-planar graphs is minor-closed.
Wrong. Consider some non 1 planar graph H (e.g. K7) and a plane embedding of it. Then there are edges with two crossings. For each such double-crossing, place a vertex in between the two crossings, and you will get a 1 planar graph that has H as a minor (by contracting one of the newly obtained edges)
(a) Give an example of a 6-connected planar graph or argue that no such graph exists.
(b) Give an example of a 5-connected planar graph or argue that no such graph exists.
(c) Give an example of a 3-connected outerplanar graph or argue that no such graph exists.
6-connected: \(deg(v)\geq6 \implies |E|\geq \frac{6n}{2}=3n, but |E|\leq 3n-6\).
5-connected: isocahedron
3-connected outerplanar (all vertices lie on outer face): There is at least one vertex of degree at most 2 which is a contradiction.
Why is the previous halfedge prev(·) stored explicitly whereas the source vertex of a halfedge is not in DCEL?
One can just go to twins target, the previous halfedge can be "far" away, if the face is large.
Give pseudocode to traverse all edges incident to a given vertex v of a DCEL.
\(s \gets \text{halfedge}(v)\\h \gets s\\\text{while }h\neq s:\\\text{do something with }h\\h\gets next(twin(h))\\\text{endwhile} \)
Give pseudocode for the operation join-face(h) in DCEL. Specify preconditions if needed.
\(\text{join-face}(h):\\h_2 \gets twin(h)\\\text{update al prev and next from } h \text{ and }h_2\\f\gets \text{new face}\text{loop starting at next(h) and set all faces to }f\)
Implement from scratch updating everything, or use other functions: (prob. slower...)
split-edge(h):
\(u \gets target(h)\\v\gets target(twin(h))\\w\gets \text{coordinates between u and v}\)
join-faces(h)
add-vertex-at(w,h)
split-face(edge coming into u,v)
Let G be a planar graph with vertex set {1, . . . , 9}. Try to find an embedding corresponding to the following list of circular sequences of faces:
(a) {(1,4,5,6,3),(1,3,6,2),(1,2,6,7,8,9,7,6,5),(7,9,8),(1,5,4)}
(b) {(1,4,5,6,3),(1,3,6,2),(1,2,6,7,8,9,7,6,5),(7,9,8),(1,4,5)}
a: draw the faces one after another, biggest one is outer face.
b: can not be planar, we have the sequence 1,4,5 appearing twice. (Would have to boarder two faces on the same side)
prove: Lemma 2.20. In a biconnected plane graph every face is bounded by a cycle.
and
Corollary 2.21. For any vertex v in a 3-connected plane graph, there is a cycle that contains all neighbors of v.
2.20: By definition a face is bounded by a closed walk. Now assume the closed walk is not a cycle. I.e. there exists some vertex v that is visited at least twice. But then the path from v to v lies entirely in F (By Jordan Curve theorem, considering the cycle, that "continues" when reaving v) and is only connected to F via v. Thus, revoming v from the graph would disconnect the graph and it would thus not be biconnected.
2.21. removing v leaves a bipartite graph and all faces v was incident to will be merged into one face and by the lemma there exists a cycle around these.
Describe a linear time algorithm that, given an abstract planar graph G and a cycle C in G, tests whether C is a facial cycle. (You may assume that planarity can be tested in linear time.)
This is equivalent to saying that G\C is connected.
test if G is planar and output a planar embedding.
G' = G\C
test if G' is connected (e.g. BFS starting on some vertex, counting how many vertices are reached)
Let G = (V,E) be a biconnected graph and let C be a collection of directed cycles of G. Assume that for every directed edge (u,v) whose underlying undirected edge {u, v} is in E, there is exactly one cycle C ∈ C that contains (u, v). Further assume that for every vertex v ∈ V, the deg(v) cycles in C that contain v can be ordered as C0,...,Cdeg(v)−1 such that for every pair u,v ∈ V and i ∈ N with (u,v),(v,w) ∈ Ci there exists an x ∈ V such that (w,v),(v,x) ∈ Ci+1 (where indices are taken modulo deg(v)). Prove or disprove: The collection C describes a combinatorial plane embedding of G.
True. Every edge used exactly once. Ordering at vertices is a rotational order, that makes sure everything is labelled counterclockwise and that you switch directions when revisiting a vertex.
Describe a family of biconnected planar graphs with exponentially many combinatorial plane embeddings. That is, show that there exists a constant c ∈ R such that for every n ∈ N there exists a biconnected planar graph on n vertices that has at least c^n different combinatorial plane embeddings.
Define a diamond: two endpoints u,v and 3 vertices in between: a,b,c and add edges u-a-v, u-b-v, u-c-v. This is biconnected and has 2 different combinatorial ambeddings.
Now, start with a cycle on k vertices and replace each edge by a diamont -> n=4k vertices and \(2^k=2^{\frac{n}{4}}=2^{\frac{1}{4}^n}\)possible combinatorial embeddings.
Prove: Theorem 2.31. A maximal planar graph on n ⩾ 4 vertices is 3-connected.
We know, that it is 2 connected and that every face is a triangle. So assume it is not 3 connected. I.e there is some cut set u,v. s.t. G\u,v=A u B disconnected. Since its 2-connected, both u and v must be connected to both A and B. But then there exists some face containing at least one vertex from A and B resp. and u and v, hence at least 4 vertices, which is a contradiction.
(a) A minimal nonplanar graph is a non-planar graph G which con- tains an edge e such that G \ e is planar. Prove or disprove: Every minimal nonplanar graph contain an edge e such that G \ e is maximal planar.
(b) A maximal-plus-one planar graph is a graph G that contains an edge e such that G \ e is maximal planar. Prove or disprove: Every maximal-plus-one planar graph can be drawn with at most one crossing.
a) Counterexample: Start with K5, subdivide one edge (add a new vertex v in the middle) this is minimal non.planar, but removing an edge does not result in maximal planar, argue with number of edges or just show: one can add an edge between x and other elements.
b)Counterexample: 3 stacked triangles, pick a vertex in the innermost and one in the outermost triangle and add that edge.
We discussed the DCEL structure to represent plane graphs in Sec- tion 2.2.1. An alternative way to represent an embedding of a maximal planar graph is the following: For each triangle, store pointers to its three vertices and to its three neighboring triangles. Compare both approaches. Discuss different sce- narios where you would prefer one over the other. In particular, analyze the space requirements of both.
Space of DCEL: O(n), but 32n (counting pointers per edge, vertex, face, and replacing |E| by 3n etc), heaviliy inflienced by number of edges
Space of other approach: 6|F|=6(2n)=12n
If maximal planar, probably latter more efficient, if we want arbitrary graph, first one
-
- 1 / 119
-
Lernkarten
Describe an algorithm to decide whether a point lies inside or outside of a simple polygon. More precisely, given a simple polygon P ⊂ R2 as a list of its vertices (v1, v2, . . . , vn) in counterclockwise order and a query point q ∈ R2, decide whether q is inside P, on the boundary of P, or outside. The runtime of your algorithm should be O(n).
Input: Polypon p1,...,pn, point q
Output inside/outside/boundary
check if on boundary:
For every (pi,pi+1): check if colinear with q i=1,..,n mod n O(n)
Draw a ray from q to infty (line starting at q going straight to the right)
For every (pi,pi+1) check if line intersects: set both line equalities = and then solve for y coordinate, if its bigger than yq, there is an intersection, increase intersection counter by one
If odd intersections: inside, even intersections: outside
Show that the bound from the Crossing Lemma is asymptotically tight: There exists a constant
c sothatforevery n,e2Nwith e n2 thereisagraphwithnverticesandeedgesthat
admits a plane drawing with at most ce3/n2 crossings. Hint: Consider a disjoint union of complete graphs.
Assume the conjecture in the script is true (i.e. \(cr(K_n)\leq c_0n^4\). Now define the following: t=e/n (roughly) and k=n/t considering k copies of Kt gives the required.
A graph is quasiplanar if it admits a simple drawing in the plane such that no three edges pair- wise cross. Denote by qp(n) the maximum number of edges in a quasiplanar graph on n vertices. Show that qp(n) 2 O(n3/2).
Consider some edge e than all edges that cross e pairwise do not cross. So the induces graph on these edges would be planar. i.e. e can at most be crossed by 3n-6 edges. So \(cr(G)\leq m(3n-6)=O(n)\) Now apply the crossing lemma:\(m(3n-6)\leq cr(G)\leq \frac{m^3}{n^2} \implies (3n-6)n^2\leq m^2\) applying a sqare root on both sides gives the desired.
Show that the maximum number of unit distances determined by n points in R2 is Ω(n log n). Hint: Consider the hypercube.
Hypercube: n=2^d (thus d=logn) vertices, deg(v)=d for all vertices, two neighboring vertices are adjacent, since they differ in exactly one coordinate, so the number of unit distances is nd/2=nlogn/2.
define a map \(\phi:\{0,1\}^d \to \mathbb{R}^n\\ \phi(x_1,...,x_d)=\sum_{i=1}^dx_iv_i\) where v_i is a unit vector and all v_is go in very similar directions (so that the sum of two can not be replicated by a 3rd) Then x,y have distance 1 iff the differ in one variable (for some i one is 0 the other is one, so they are exactly v_i apart)
Omega notation: we just need a lower bound.
In the proof of Theorem 4.6, would the argument in Case 2 also work if the point p was chosen to be a vertex of P in T◦ that minimizes the Euclidean distance to v?
Doesnt work. Contruction: draw p close to uw and the add two points forming a line between v and p.
Every triangulation of a simple polygon P with n > 4 vertices contains at least two triangles that serve as ears in P.
Consider the dual graph. (one node per face=triangle) this is a tree, since for a cycle we would have to have an internal vertex. An ear is a leaf (only one neighbor implies that only one of the 3 sides is interior. and a tree on at least 2 nodes has at least two leaves. (We need 4 vertices for two faces)
Convert Theorem 4.6 into an O(n2) time algorithm to construct a triangulation for a given simple polygon with n vertices.
input: simple polygon
output:triangulation
if #vertices=3: return polygon
sort vertices lexicographically (O(nlogn))
for v in sorted vertices:
consider the triangle uvw
if relint(uw)in int(P): (O(n))
add uwv to triangulation, triangulate P\v
else:
find p with shortest distance (O(n))
split P along vp and triangulate these (check for every vertex in what halfspace they lie-> O(n))
Describe a family \((P_n)_{n\geq3}\) of simple polygons such that Pn has n vertices and at least \(\lfloor\frac{n}{3}\rfloor\) guards are needed to guard it.
Contruct a crown. (n=3 a triangle) and for every additional 3 vertices get an additional jag make the jags have some space in between, such that you can not place a guard in the bottom rectangle such that it sees two jags, a guard has to be positioned between where the extentions of the left and right lines of it lie.
What is a simple polygon/a simple polygon with holes? Explain the definitions and provide some examples of members and non-members of the respective classes. For a given polygon you should be able to tell which of these classes it belongs to or does not belong to and provide justifications.
simple polygon: compact region \(P \subset \mathbb{R}^2\) with boundary simple closed curve consisting of finitely many consecutive line segments.
with holes: \(P=F\backslash \bigcap_{H\in \mathcal{H}}H^°\) with F simple polygon,\( \bigcap_{H\in \mathcal{H}}H \subset F^°, \mathcal{H}\) collection of pairwise disjoint simple polygons.
examples see script, (e.g. 4.1)
What is a closed/open/bounded set in Rd? What is the interior/closure of a point set? Explain the definitions and provide some illustrative examples. For a given set you should be able to argue which of the aforementioned properties it possesses.
open U: for every point p there exists some epsilon, such that the Ball with radius epsilon centered at p lies entirely in U
closed: complement open
bounded: is contained in some ball around the origin.
What is a triangulation of a simple polygon? Does it always exist? Explain the definition and provide some illustrative examples. Present the proof of Theorem 4.6 in detail.
Triangulation of P is a collection of triangles, such that they 1. cover P , 2.vertices of all T are vertices of P, 3. \(\forall T_1,T_2: T_1\cap T_2\) is a common vertex/edge or empty. Every simple polygon has a triangulation.
proof. induction on number of vertices, n=3 is a triangle. For larger n, take x as lexicographically (according to x,y coordinates) smallest vertex and let u and w be its neighbors. Then uvw is a left turn bc x smallest. Now consider the line segment between u and w:
1 case: \(relint(\bar{uw})\subset P^° \implies uvw \) triangle of the triangulation and when taking this away and adding the edge uw, we are left with a smaller polygon.
2.case: not as above. Then choose point p in uvw and edge point of P that maximizes the distance to the line uw. seperate the polygon along the line between v and p.
Every triangulation consists of n-2 triangles and 2n-3 edges
How many points are needed to guard a simple polygon? Present the proofs of Theorem 4.9, Lemma 4.16, and Theorem 4.17 in detail.
\(\lfloor\frac{n}{3}\rfloor \).
4.9. Every triangulation of a simple polygon P with n > 4 vertices contains at least two triangles that serve as ears in P.
proof. Consider dual graph is a tree and a tree has at least two leaves
4.16: every triangulation is 3-colorable
proof. induction, remove ear, put back in and assign it color that the other two vertices in triangle dont have.
4.17 every simple polygon with n vertices can be guarded using at most \(\lfloor \frac{n}{3}\rfloor\)guards.
proof. place guard at color that occurs the least in 3-coloring
How about higher dimensional generalizations? Can every polyhedron in R3
be nicely subdivided into tetrahedra? Explain Schönhardt’s construction.
No, twisted prism. (figure 4.4, new added epigonals can not be part of tatrahedron)
Prove Carathéodory’s Theorem.
Theorem 5.12 (Carathéodory [3]). For any P ⊂ Rd and q ∈ conv(P) there exist k ⩽ d+1 points p1,...,pk ∈ P such that q ∈ conv(p1,...,pk).
proof. since q is in conv hull, \(q=\sum_{i=1}^{n}\lambda_ip_i.\) By induction, if \(n\leq d+1\), we are done. So assume n>d+1. But then the pis are dependent, i.e. \(\exists \mu_i,...,\mu_n \text{ not all 0, s.t. } \sum_{i=1}^n\mu_ip_i=0, \sum_{i=1}^n\mu_i=0.\\ \text{ w.l.o.g. assume }\mu_n\neq0. p_n=\sum_{i=1}^{n-1}\frac{\mu_i}{-\mu_n}p_i \text{ and } -\mu_n=\sum_{i=1}^{n-1}\mu_1 \iff \sum_{i=1}^{n-1}\frac{\mu_i}{-\mu_n}=1.\)
Then we can rewrite q as \(q=\sum_{i=1}^{n-1}\lambda_ip_i+\lambda_n(\sum_{i=1}^{n-1}\mu_ip_i)=\sum_{i=1}^{n-1}(\lambda_i+\lambda_n\mu_i)p_i\) where the sum of coefficients is 1 and it only depends on n-1 ps. i.e. its in the convex hull of p1,...pn-1 and by induction, we are done.
Given a finite point set P ⊂ Rd, a point q ∈ conv(P), and a point x ∈ Rd. Show that there exists a subset P′ ⊆ P of at most d points such that q ∈ conv(P′∪{x}).
P u {x} is of size d+2. So by Caratheodory, there exists some at most d+1 sized subset s.t. q is in its convex hull. But the point that we take out is not unique (see proof of caratheodory, there is multiple pis with non zero coefficiant). Thus, we can take out a point that is not x.
Prove that for every n, there is a set of n points in Rd such that for any p in Rd, there is an open halfspace containing \(\lfloor\frac{nd}{d+1}\rfloor\) of the points, but not p.
Consider the d+1 rays vi of the standard simplex (e.g. equilateral triangle in R2) place roughly n/(d+1) point along each ray vi, such that they have some distance to the origin. Now for any point p, let vi be the ray that its closest to. Define the halfspace by the hyperplane orthogonal to v_i, containing p. (shift a little bit towards the origin, s.t. p lies on one side). Then on one side there is p and at most all points on vi. all other rays lie on the other side. Thus the other side contains at least d(n/d+1) points (if one wants exactly d(n/d+1) points, shift the hyperplane ever further towards the origin, such that really all ponits on vi lie on the same side as p) if the closest vector to p is not unique, tild the hyperplane slightly.
Show that the Separation Theorem does not hold in general if not both of the sets are convex.
Draw a kind of kidney shaped thing and then a thin structure that is very close to one side of it and such that its closest point makes a line that is perpendicular to one that crosses the other side of the kidney.
Prove the following:
For a compact set P Rd we can characterize conv(P) equivalently as one of
(a) the set of all convex combinations of points from P;
(b) the set of all convex combinations formed by d + 1 or fewer points from P;
(c) the intersection of all convex supersets of P;
(d) the intersection of all closed halfspaces containing P.
You can assume the equivalence (a) ⇐⇒ (c) since it has been proved in the lecture.
b is equivalent to c by Caratheodory (proof)
c contained in d: halfspace is a superset. if point not in c then there exists seperating hyperplane, thus not in d.
Let P = (p0, . . . , pn−1) be a sequence of n points in R2. Someone claims that you can check by means of the following algorithm whether or not P describes the boundary of a convex polygon in counterclockwise order:
bool IsConvex(p0, . . . , pn−1) { for i = 0, . . . , n − 1:
if (pi, p(i+1) mod n, p(i+2) mod n) form a rightturn: return false;
return true; }
Disprove the claim and describe a correct algorithm to solve the problem.
Disprove: Things can cross (draw for example a prezel)
Correction: right turn and dont cross
Let P ⊂ R2 be a convex polygon, given as an array p[0...n − 1] of its n vertices in counterclockwise order.
a) Describe an O(log n) time algorithm to determine whether a point q lies inside, outside or on the boundary of P.
b) Describe an O(log n) time algorithm to find a (right) tangent to P from a query point q located outside P. That is, find a vertex p[i], such that P is contained in the closed halfplane to the left of the oriented line qp[i].
a) Binary search triangle it might lie in: consider all triangles p[0]p[i]p[i+1] and check which one point lies in: fix angle, that p[0] forms with q. start by considering p[0]p[1]p[n] if outside that angle it is not in polygon. Then consider p[0]p[1]p[n/2] and so one to find corresponding triangle. Then check if dist(p[0],q)<dist(p[0],p) where p is the intersection of the line passing through p[0] and q and the line segment p[i]p[i+1] (the triangle q lies in).
b) Binary search on the vertices: for vertex i: check if the curve q,p[i],p[i-1] and the curve q,p[i],p[i+1] are left turns. Then we found the right vertex. Else if with p[i+1] is right turn, search in greater indices and vice versa. If both are right turns, it is a left tangent and we can go in either direction (not 100% sure) I is binary search index (start in middle and always take the middle index of the remaining)
How is convexity defined? What is the convex hull of a set in Rd? Give at least three possible definitions and show that they are equivalent.
convexity: P convex, if for any two p,q in P the line segment between p and q lies entirely in P. Convex hull: 1) intersection of all convex supersets of P 2) set of all convex combinations of P 3) Intersection of all halfspaces containing P
proof.
What is a centerpoint of a finite point set in Rd? State and prove the centerpoint theorem (Theorem 5.17) and the two classic theorems used in its proof (Theorems 5.11 and 5.15).
Thm(Radon) Any set P subset Rd of d+2 points can be partitioned into two disjoint subsets P+, P- such that their convex hulls have non empty intersection. They are affinely dependent, find a discription of 0 with not all coefficiants 0 and spilt them into terms with positive/negative coefficiants. Then we can express their common point by a linear combination where each coefficiant is divided by the sum of all coefficiants in P+=- coefficients in P-
Thm (Helly): \(\mathcal{C}=\{C_1,...,C_n\}, n\geq d+1\) convex subsets of Rd, s.t. any d+1 sets have non empty intersection, then the intersection of all n of them is nonempty.
proof.induction on n: n=d+1 is clear. for greater, take Di intersection of all but Ci take a point in there Then by Radon we can seperate it into P+ and P- and find a point p in their intersection. Show, this is in all Ci: take some pi in Di. If it is in P-, Then conv(P+) is in Ci and thus p is in Ci and analog for pi in P-.
center point thm: Every set P ⊂ Rd of n points has a centerpoint.
We can assume P contains at least d+1 points (Otherwise embed in a subspace) \(\mathcal{A}:=\{P\cap H|H \text{ open halfspace }, |P\cap H|>\frac{dn}{d+1}\} = \{A_1,..,A_k\}\)Ci=conv(Ai). We have that any d+1 sets in fancy A contain at least dn/(d+1) points. Thus the total occurance of points is greater than (d+1)(dn/(d+1)=dn and thus there exists a point occuring more than d times so it must be in all d+1 sets.
What does it mean to compute the convex hull of a set of points in R2? Discuss input and expected output and possible degeneracies.
Input: point set P, output: Q subset of P, s.t. all point lie in conv(Q) and Q is ordered anticlockwise. Degeneracies: colinear points. (Some algorithms start by smallest x value: resolve: lexicographically order them)
How can the convex hull of a set of n points in R2 be computed efficiently? Describe and analyze (including proofs) Jarvis’ Wrap, Graham Scan, and Chan’s Algorithm.
See script/ hand written flashcards
Is there a linear time algorithm to compute the convex hull of n points in R2? Prove the lower bound and define/explain the model in which it holds.
No, lower bound: nlogn, (or nlogh) using CHans divide and conquer algo for h=min(2^2^ i, n)
Which geometric predicates are used to compute the convex hull of n points in R2? Explain the two predicates and how to compute them.
left/right turn: determinant of matrix, what side of a hyperplane
Prove or disprove that every minimum weight triangulation (that is, a triangulation for which the sum of edge lengths is minimum) is a Delaunay triangulation.
False: counterexample: A=(0,0),B=(2,0),C=(2,1),D=(0,1.1) is convex quadrilateral, AC is shorter diagonal, but delauney chooses AD.
The Euclidean minimum spanning tree (EMST) of a finite point set P ⊂ R2 is a spanning tree for which the sum of the edge lengths is minimum (among all spanning trees of P). Show:
(a) Every EMST of P is a plane graph.
(b) Every EMST of P contains a closest pair, that is, an edge between two points
p, q ∈ P that have minimum distance to each other among all point pairs in P.
(c) Every Delaunay Triangulation of P contains an EMST of P.
a) Assume that two edges ac, bd cross, then consider the quadrilateral abcd. remove the longer one of ac and bd, w.l.o.g assume this is ac. Then either a or c are connected to bd since its a spanning tree. again w.l.o.g assume thats a. But then at least one of cb, cd must be shorter than the diagonal ac, so replacing ac by the shorter of the two is a spanning tree with shorter total edge lengths.
b) assume there is no closest pair. Then consider some closest pair p,q. Then there exist a path from p to q including some edge s that would disconnect p and q, but then we can replace s by pq and get a sharter spanning tree.
c) Assume an EMST edge is not delauney, i.e there is a point r inside the circle around pg (with circumference d(p,q)) but then d(p,r)<d(p,q) and d(r,q)<d(p,q) but then again either p or q must be connected to r after removing pq and for the other one add the edge to r to obtain a smaller tree.
What is a triangulation? Provide the definition and prove a basic property: every triangulation with the same set of vertices and the same outer face has the same number of triangles
set of triangles, s.t. they cover the space (Or convex hull of point set) sum(V(T))=P and intersection of two triangles is either vertex, edge or empty. Outer face(convex hull) is always part of triangulation and internally it is a maximal planar graph.
What is a triangulation of a point set? Give a precise definition.
collection of triangles, s.t.
Union of triangles is conv(P)
union of vertices of T =P
intersection of 2 distinct triangles is vertex, edge or empty
Does every point set (not all points on a common line) have a triangulation? You may, for example, argue with the scan triangulation.
Yes. for P=(p1,...pn) lexicographically ordered. m=min, s.t. p1,..,pm are not all on a line. connect pm to pi for i=1,..m-1. Then add point pi one by one: connect to all "visible" vertices (it is not in convex hull of previous vertices, since lexicographically ordered)
What is a Delaunay triangulation of a set of points? Give a precise definition.
A triangulation is Delaunay, if for every triangle there exists a circle C (circumcircle), s.t. the vertices of the triangle lie on its boundary and no other vertex of P lies strictly in C
What is the Delaunay graph of a point set? Give a precise definition and a
characterization.
Delauney graph is the graph containing all edges that appear in every delauney triangulation. If delauney triangulation is unique, the graph is the unique delauney triangulation.
How can you prove that every set of points (not all on a common line) has a Delaunay triangulation? You can for example sketch the Lawson flip algorithm and the Lifting Map, and use these to show the existence.
Every point set has a triangulation. E.g. scan triangulation. Lawson flip algo: for two neighboring triangles T, T', s.t circumcircle of T strictly contains vertex of T': flip diagonal.
terminates: project triangulation onto unit paraboloid: (x,y) -> (x,y,x^2+y^2). The lifted circle is the intersection of the hyperboloid with a unique hyperplane, points are strictly inside the Circle, iff the are below the hyperplane. Then a flip changes a mountain into a valley (quadritaleral of two triangles is a tilted, one diagonal is above the other and is by flip turned into the other.) Thus, the lifted triangulation grows monotonely towards bottom and one an edge is changes, it stays that way.
Is Correct: (I.e. is Delaunay) locally by definition. Globally: Assume there is some non delauney triangle. among all, take pair (T,p) s.t. p is in circumcircle C of T and distane between T and p is smallest. If closest point to p an T is on some edge e: That edge is incident to another triangle with point q outside C (otherwise not locally delauney) but then that triangle has a circumcircle, that contains complete left side (or right, if p on right) of the circumcircle of T, i.e. also p, but then this triangle would be closer to p. If the closest point to p on T is a vertex: argue with angles: take pair with angle closest to 90 degrees and again construct T' with q and show this has better angle.
When is the Delaunay triangulation of a point set unique? Show that general position is a sufficient condition. Is it also necessary?
General position sufficient: No 4 vertices lie on a common circle. Thus for every triangle, its circumcircle can not contain any other points on the boundary. Thus a triangle is either Delaunay and thus in the triangulation or not and thus not in it (No choice in a quadrilateral) is is not sufficient: Colinear dont affect it (unless all are colinear)
What can you say about the “quality” of a Delaunay triangulation? Prove that every Delaunay triangulation maximizes the smallest interior angle in the triangulation, among the set of all triangulations of the same point set.
no narrow triangles, unless not otherwise possible.
proof. Show that a flip maximizes minimal angle. Assuming general position, consider a quadrilateral with a diagonal that will be flipped. If we consider a quadrilateral with all 4 vertices on a circle, we have pairs of angles that are the same (draw both diagonals and then always on both sides of a triangle angles are the same) So now consider the circumcircle of one of the non- Delaunay triangles of the quadrilateral then the last point of the quadrilateral lies inside. We can then update some of the angles (only in terms of greater or smaller than the 4 remaining angles. When flipping the diagonal, we can compute and see that every of the 6 new angles is greater than some of the 6 old angles.
For a sequence of n pairwise distinct numbers y1, . . . , yn consider the sequence of pairs (min{y1, . . . , yi}, max{y1, . . . , yi})i=0,1,...,n (min ∅ := +∞, max ∅ := −∞). How often do these pairs change in expectation if the sequence is permuted randomly, each permutation appearing with the same probability? Determine the expected value.
pair changes at step i, iff yi is either new min or new max. p(yi is new min)=p(yi is new max)=1/i. Thus in general 2/i. (except for i=1, where the new yi will be min and max at the same time, i.e. p=1. So expected number of changes: \(1+\sum_{i=2}^n\frac{2}{i}\)
What conditions should the three “far-out” points a,b,c satisfy? Explain the reason.
The triangle abc should strictly include all points from P. So that the delauney triangulation is a max planar graph (avoinds special cases). So that we can add the points from P one by one uniformly at random, since we already have a triangulation (of abc).
Describe the algorithm for the incremental construction of DT(P): how do we find the triangle containing the point ps to be inserted into Ds−1? How do we
transform Ds-1 into Ds? How many steps does the latter transformation take?
Finding the triangle: history tree of all triangles that ever existed, directed such that a node has triangles it turns into as children. As abc is on top, it defnitely contains ps and then always exactly one child contains it. Ds-1 is turned into Ds by interting ps into triangle and splitting that triangle into 3 and then doing lawson flips until graph is delauney. number of flips= ds-3, where E[ds] leq 6. (plus the insertion of ps)
What are the two types of triangles that the history graph contains?
Valid: created at step r and part of Dr
ephemeral: created at step r and not part of Dr (directly flipped away)
