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
-
Flashcards
Consider k convex polygons P1, . . . Pk, for some constant k 2 N, where each polygon is given as a list of its vertices in counterclockwise orientation. Show how to construct the convex hull
of P1 [...[Pk in O(n) time, where n = ki=1ni and ni is the number of vertices of Pi, for 1 i k.
Construct lower and upper convex hull. start by lexicographically smallest for lower, for each polygon order them in a queue as they appear (counterclockwise) starting from lexicographically smalles vertex. Check for all Pi first in Queue which line is lowest. For this Pi, also check 2nd vertex in queue, add lower tangent vertex to lower convex hull. Discard all points with smaller x coordinate and continue until you reach overall lexicographically largest vertex. Upper analog. Runtime: O(kn) but since k is constant O(n)
(a) What is the bisector of a line l and a point p∈R2 \l, that is, the set of all points x∈R2 with||x−p||=min_{r∈l}||x−r||?
(b) For two distinct points p,p0 in R2, what is the region that contains all points whose distance to p is exactly twice their distance to p0?
a) a paraboloid
b) a circle around p0, crossing the line between p and p0 at 1/3 of the distance and being centered at a point on that line but 1/3 after the point p0.
Consider the Delaunay triangulation T for a set P ⊂ R2 of n ⩾ 3 points in general position. Prove or disprove:
(a) Every edge of T intersects its dual Voronoi edge.
(b) Every vertex of VD(P) is contained in its dual Delaunay triangle.
a) not true. Counterexample: consider triangle pi,pj,pk pretty shallow and symmetric and let pk be the middle point. Then there is only one voronoi vertex, that lies "over" the triangle so pipj passes through VP(k) and thus not through its "own" edge.
b) not true, one triangle can contain multiple points and another none. See picture
Prove: A star-shaped polygon, given as a sequence of n greater or equal than 3 vertices and a star-point, can be triangulated in O(n) time.
Start by connecting all n vertices to the star point. Then walk around the boundary, whenever there is a convex point, flip the line connecting it to the star point within its quadrilateral.
For O(n): make a list (or queue) of convex vertices. Whenever you flip ad edge to v: remove v from list and check if its 2 neighbors are now convex.
What is the Voronoi diagram of a set of points in R2? Give a precise definition and explain/prove the basic properties: convexity of cells, why is it a subdivision of the plane?, Lemma 8.6, Lemma 8.8.
subdivision of the plane into voronoi cells= set of closests points to p. divides plane because every point is closest to some point. (If to multiple its on edge/vertex. Convex, since intersection of halfspaces. Vertex incident to (at least) three cells, edge vertex is endpoint of at least 3 edges (both proven by convexity) center of circle through (at least) 3 points: v incident to VP(1),...VP(k). Then p1,...pk simultaneously closest to v. (distance to v is the same for all)
What is the correspondence between the Voronoi diagram and the Delaunay triangulation for a set of points in R2? Prove duality (Theorem 8.9) and explain where general position is needed.
Dual graph of voronoi graph (where we hoose pis as representatives of the faces) is delauney triangulation (if general position) Otherwise, there is some convex polygons that need to be triangulated, but every triangulation will be Delaunay.
proof. vertices are trivially the same. Edge of dual of voronoi: pipj if cells unbounded: on boundary and thus also in del. triangulation, else there exists a cyckle pipjpk and thus pipj is an edge of del.t. For the other direction, every edge of the del. triangulation is on some circumcircle centered at v and thus the edges pipjpk are all in the dual graph.
How to construct the Voronoi diagram of a set of points in R2? Describe an O(n log n) time algorithm, for instance, via Delaunay triangulation.
Construct delauney triangulation in O(nlogn) and transfer it to voronoi cells in O(n) (find midpoints of all circles of triangles) and connect two adjacent ones if triangles were adjacent.
What is the Post-Office Problem and how can it be solved optimally? De-scribe the problem and a solution using linear space, O(n log n) preprocessing, and O(log n) query time.
Post office: in a town, what is the closest post-office for a person at point q? (inside convex hull of P)
Solve: Do Voronoi dagram. (As graph) and then use Kirkpatricks hirachy to determine what triangle q lies in: construct sequence of triangulations T0,..,Th s.t. T0 is initial triangulation, Th is a single triangle. And start looking for q starting in Th going back down. In each step remove at least 1/18 vertices of degree at most 8 (greedy: remove vertex and delete v plus neighbors from those that can possibly be removed (of degree at most 8)) We have that the vertices of degree at most 8 are at least n/2. ( by splitting vertices into set of greater and less or equal than 8 degree)
How does Kirkpatrick’s hierarchical data structure for planar point location work exactly? Describe how to build it and how the search works, and prove the runtime bounds. In particular, you should be able to state and prove Lemma 8.22 and Theorem 8.17.
Runtime: In every step at least ni/18 vertices are removed. so we get that \(n_i\leq (\frac{17}{18})n_{i-1}\leq...\leq (\frac{17}{18})^{i}n\) as the time cost for removing vertices. and in total building the hirarchy thus costs \(\sum_{i\in \mathbb{N}}(\frac{17}{18})^{i}\leq18n\). Number of levels: log_{18/17}n. In total: 3ch=3 8 log_{18/17}n<292 logn.
The standard projective duality transform is
• incidence preserving: p ∈ l ⇐⇒ l∗ ∈ p∗ and
• order preserving: p is above l ⇐⇒ l∗ is above p∗.
\(p=(a,b), l: y=cx+d \\p\in l \iff b=ca+d \iff -d=ac-b \iff l^*=(c,-d)\in p^*:y=ax-b\)
for above, replace= by <.
Let F be a family of vertical line segments such that for each three of them, there exists a line that intersects all three. Show that there exists a line which intersects all line segments in F.
We can translate it to its dual. A vertical segment Si is a segment between (xi,y1(i)) and (xi,y2(i)) (w.l.o.g secong y larger). A non-vertical line f:y=mx+b intersects this iff y1(i)<=mxi+b<=y2(i) iff y1(i)+mxi<=b<=y2(i)+mx Not seeing all lines as points (m,-b), every segment gives us a subspace of R^2 shaped like a ribon (two parallel lines and everything in between is valid.). Denote this by Ri. Now, we cann apply Hellys theorem, stating, that if any 3 sets have non-empty intersection, then the whole set also has non-empty intersection.
The X + Y sorting problem is the following: given two sets X and Y of ndistinctnumberseach,sortthesetX+Y={x+y:x∈X, y∈Y}. Itisanopen problem whether this can be done in o(n2 log n) time.
Prove that X + Y sorting reduces (in O(n) time) to the problem of sorting the
2n lines pq by slope, for all pairs {p,q} from a set of 2n points.
We construct the follwoing 2n points: For x in X point (0,-x) and for y in Y: (1,y).
Then the slope for two points from x or y is (-)infinity and thus not relevant and the slope from a point in X and one in Y is (y-(-x))/(1-0)=y+x. So sorting the slopes of these lines is exactly sorting X+Y. runtime: construct 2n points: O(n). (We take the slopes of any pair, but that is part of the slopes problem)
Show that the following variation of 3-Sum—call it 3-Sum◦—is 3-Sum- hard: Given a set S of n integers, are there three (distinct) elements of S that sum up to zero?
A problem X is 3-Sum-hard if every 3-Sum instance of size n reduces to solving a constant number of X instances of size O(n), within O(n2−ε) reduction time for some constant ε > 0.
Triple the set S and then find 3 "distinct" numbers. (This enables triples with multiple appearances to be valid) (Or faster: only triple if there is a 0, otherwise only double, cause 3 times something non-zero makes no sense)
The goal of this exercise is to develop a data structure for halfspace range counting.
(a) Given a set P ⊂ R2 of n points in general position, show that it is possible to partition this set by two lines such that each region contains at most ⌈n/4 ⌉ points.
(b) Design a data structure of size O(n) that can be constructed in time O(n log n) and allows you, for any halfspace h, to output the number of points |P ∩ h| of P contained in this halfspace h in time O(n^α), for some 0 < α < 1.
a) Divide points randomly into 2 sets, find line bisecting both by ham sandwich, then "recolor" them according to what side of the line they lie on and again find a bisecting line.
b) We divide the plane into 4 sections. We know there is an algorithm finding a ham sandwich cut in O(n). (Or eq. finding two lines) So doing this requirsively for all quaters and constructing a tree, where a child means its one of the parents quaters needs \(O(n)+O(n/4)+(n/8),...+O(n/2^k)=O(nlogn)\) time.
That tree is of size O(n). Every node contains the number of vertices (size) of its region and information on where it lies. To determine the number of vertices contained in h, notice, that one of 4 quarters is always either fully contained in h or not contained at all. So we only need to continue the paths on 3 of 4 children, and thus get a runime of 3T(n/4)+O(1) per step and thus in total an \(O(n^{log_43})\) query.
Show that λ1(n) = n and λ2(n) = 2n − 1.
lambda_1(n): There can be no subsequence of length 3. Meaning no symbols a...b...a. But if a sequence is longer than n, by pigeonhole, one element must appear at least twice. And since it can not appear in consecutive positions, there must be some element in between.
lamda_2(n): No sequence of the form abab. Induction: clear for n=1. Fix some element a. Then a sequence is of the for S0aS1a...aSk where Si is a part of the sequence not containing a and S0 and Sk are possibly empty. Then all Sis must be disjoint. And by the induction hypothesis we have |Si|<=(#symbol in Si) -1. Then the total length is \(|S0|+\sum_{i=1}^k|Si|+1\leq 2(T0-1)+2(\sum_{i=1}^kTi-1+1)=2n-1\) where Ti is the number of different elements in Si.
Show that every (n, 2)-Davenport-Schinzel sequence can be realized as the lower envelope of n parabolas.
For every parabola, we get a first and a last appearance. This is an Interval Ix for parabola x. Then these Intervals (considered as open intervals) are either disjoint (x can only appear before y) or contained in one another. E.g Ix inside Iy. But then y is a wider parabola und thus we can only have the sequence y....yx...x...y....y.
Let P ⊂ R4 be a finite set of points in general position and let P be the polytope defined by the convex hull of P. Show that f3 ⩾ f0.
The vertex edge graph is 4-connected so \(2f_1 \geq 4f_0\) and every every facet has at most 4 ridges and each ridget is incident to 2 facets. Thus \(2 f_3 \geq f_2.\) Plugging this into Euler Oncaree formula yields the desired.
Characterize all polytopes in R3 that are both simple and simplicial.
Only 3-simplex. deg(v)=3 for all v. Thus 2|E|=3|V|. Simplicial implies, that every facet is a triangle. Thus 2|F|=3|E| and the underlying graph is max planar. Thus |E|=3|V|-6. Only possible with |E|=6 and |V|=4
Alternative: Start at some vertex v and connect it to 3 vertices xyz. since every face is a triangle, they must be pairwise connected.
What is a polytope? Give a definition and provide a few examples.
Polytope: conv hull of finite point set, intersection of finitely many halfspaces, bounded.
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.
