Q1

a: smallest enclosing ball, O(n³) worst case, O(n) expected.

b: convex hull, O(n) time,

since the chain is already sorted on x-coordinate. (so no need to sort again in the graham scan algorithm.)

c : kd-tree, O(n^2/3 + k).

d : EMST, O(nlog n) via Delaunay Triangulation.

e : Insert into Arrangement, O(n) time

by the zone Theorem

f: cutting tree O(n^2 + ε), for some arbitrarily small ε > 0

(This was not covered this year)

using a multi level cutting tree.

g: triangulating, O(n²) time:

there are O(n²) bounded faces, of total complexity O(n²); every such face is convex (and thus y-monotone). So triangulation it takes linear time in the complexity of the face.

Q2:

a

interval tree: balanced binary tree on the endpoints of the intervals. The root u corresponds to the median x-coordinate m and stores all intervals containing this midpoint. Intervals left of m are stored in the left subtree, and right of m in the right subtree. u stores the intervals twice: once sorted on left endpoint and once on right endpoint

segment tree: balanced BST on endpoints of intervals. leaves correspond to atomic intervals defined by consecutive endpoints. Internal nodes correspond to the union of the atomic intervals of its leaves. Intervals are stored in a node v if the interval covers the inverval of V but not of its parent.

b

prefer interval tree: O(n) space rather than O(nlog n)

prefer segment tree: query result can be represented as O(log n) canonical subsets, this is useful for building multilevel structures.

Q3

<<imagine some wonderful figure here that shows the geometries described below>>

Let $\overline{pq}^*$ be a strip bounded by two parallel lines p^* and q^* with q^* above p^*, and let r^* be a line steeper than q^* that intersects a line s^* that is contained in $\overline{pq}^*$ in a point ℓ^*. (That the ‘b’-coordinate (i.e. the intercept) of r^* is smaller than that of p^* follows from this as well.)

Q4

a

if p occurs on CH there is a line ℓ through p that bounds an empty half-plane. consider the half-line in this half-plane starting in p, that is perpendicular to l. Any point on this half-line is strictly closer to p than to any other point in p (as any circle with p on its boundary centered on the line is empty.)

b

Every vertex in VD uniquely corresponds to a triangle in the Delaunay triangulation. So we have to prove that DT contains 2n − 2 − k triangles. This follows from Euler’s formula, which states that (for a connected graph, like DT):

V − E + F = 2

We have n points/vertices, so V = n

There is one outer face, and T triangles, hence F = T + 1.

Every edge appears in two faces. every triangle has 3 edges, the outer face has k edges. So

2E = 3T + k.

Combining this gives us

2n − 2E + 2(T + 1) = 4

≡ 2n − 3T − k + 2T + 2 = 4

≡ 2n − T − k − 2 = 0

≡ 2n − k − 2 = T

as claimed.

Q5

a

a trapezoidal decomposition (together with the search dag that is built on the trapezoidal decomposition using a RIC algorithm).

b

<<see notes on the website for something more detailed>>

fix a query point q, which fixes a path in the query DS. Now analyze how many nodes on this path are added because of segment s_i. There are at most three anyway since we only add nodes at the bottom of the structure, and only if P actually ends in a trapezoid created in step

The probability that our particular trapezoid containing q was

created in step is is 4/i. So we get something like sum_i = 1ⁿ12/i = 12 * H_n = O(log n)

c

O(nlog n + mlog n) time (building the data structure, and then querying it.)

d

The idea was to use a sweep line that sweeps a horizontal line from top to bottom. The status structure is simply the list of edges of S intersected by the sweep line from left to right. We store them in a BST. The events are when we sweep over a vertex of S or a query point. Handling an event requires O(klog n) time where k is the degree of a vertex (essentially k=0 for query points) since they involve O(k + 1) queryies/updates to the status structure.

( Admittedly, this this approach actually gives you a running time of O((n + m)log (n + m)), which may be slightly slower than the O(nlog n + mlog n) bound. if m is huge compared to n. )

Build a segment tree with fractional cascading on the line segments, then query it.

e

(not covered this year)

degenerate inputs (i.e. multiple points with same coordinates etc) -> symbolic pertubation

floating point issues -> use exact real arithmetic

Q1

a: smallest enclosing ball, O(n3) worst case, O(n) expected.