Q1

a

O(nlog n) time.

b

O(log²n + k) time.

c

O(n) time.

d

O(nlog n) time.

e

O(n) time.

Q2

a

O(n): consider some sufficiently large bounding box that contains all vertices of 𝒜. It follows that any unbounded cell intersects the boundary of the bounding box. Hence, every unbounded cell is intersected by one of the four supporting lines of the edges of this box. The result now follows by applying the zone theorem 4 times.

b

Pick n − 1 (almost) parallel lines ℓ₁, .., ℓ_n − 1 that all intersect a single line ℓ_n. Each of the first n − 1 lines creates one vertex on an unbounded face. Therefore the above bound is tight.

(There are many other ways of getting such a bound.)

Q3

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

$\overline{qr}^*$ is a double wedge, whose intersection point is ℓ^*. Line r^* is the steepest of the two bounding lines (which is thus at the bottom left of ℓ^*). S^* is a vertical linesegment at a = 0 that lies below r^* and q^*. line p^* lies below this line segment S^*, and has a slope in between that of q^* and r^*.

Q4

DT is a connected planar graph, so we use Eulers formula: V − E + F = 2

We have V = n

Let T be the number of triangles, then we have F = T + 1. Moreover, we have 2E = 3T + k since every triangle consists of three edges, the outer face consists of k edges, and every edge appears in two faces.

We thus get: n − E + T + 1 = 2  ≡ 2n − 2E + 2T + 2 = 4  ≡ 2n − (3T + k) + 2T + 2 = 4  ≡ −T = 2 − 2n + k  ≡ T = 2n − k − 2

Q5

a

Shuffle the halfplanes; we add them one by one, while maintaining the lowest point that appears in all halfplanes. if the current optimal solution is contained in the new halfplane, continue. If it lies outside the current halfplane, the new lowest point must lie on the boundary l of this halfplane. To find this point, we use 1D linear programming; i.e. we iterate over all halfplanes that we already encountered (every halfplane defines a feasilble half-line; testing if there is a feasilble point/finding the lowest such point) cana be done in O(n) time.

b

Method (ii) is (in expectation) faster than method (i). (O(n) expected time vs O(nlog n) (worst-case) time).

c

Method (ii) gives you only one possible removal direction. Whereas method (i) gives all possible directions. That may be desirable when there are other (say non geometric) constraints on how to remove the shape.

Q6

Use a sweepline algorithm sweeping a vertical line ℓ from left to right. We maintain the edges currently intersected by ℓ in a BST. The events are vertices (since those are the only places these edges change). The eventqueue is just a sorted list

At every event v at x_i, we update the status structure by inserting edges for which v is the left endpoint and delete those for which v is the right endpoint. We then create a fresh copy of the status structure and save it in D[i].

We sort the events O(n) events. The BST actions at each event O(k * logn) time, where k is the degree. The total degree over all vertices is O(n), so overall O(nlog n) time. Copying the BST is O(n) time. So in total we spend O(n²) time.

Q7

a

We can retrieve all segments that have an endpoint in R by using a 2d range-tree, this reports all endpoints in O(log²n + k′) time, where k′ is the number of reported endpoints. for every reported endpoint, we can access the segment it is an endpoint of in constant time, and check: (i) if this is the only endpoint in R, and just report it, or (ii) if the other endpoint is also in R. In case of (ii), we can, say report the segment only when the current point is the left endpoint.

During this reporting, every valid segment is encountered at most twice (by both its endpoints). Hence k′ = O(k).

b

When a segment has both endpoints inside the query range R, it is counted twice. Not all segments are counted twice.

c

We build two separate range trees, one storing only the left endpoints, one storing only the right endpoints. The one for the right endpoints is just a normal range counting DS. For the tree with left endpoints we do the following.

For each secondary node v, for each left endpoint in P_v, let R_v be the set of corresponding right endpoints. We build a range tree (for counting queries) on those points.

We now query the tree on right endpoints to find all segments whose right endpoint lies in the query range (this includes the ones that also have their left endpoint in the query range).

We then query the left-endpoint tree to find only the left endpoints whose right endpoint is outside the query range. These points are represented by O(log²n) canonical sets. For each such canonical subset we can now count the number of segment whose right endpoint is outside the query range. (This requires actually four queries in each such tree; each taking up to O(log²n) time)

This results in O(log⁴n) query time.

(Alternatively: we can build a 4-level range tree to count exactly how many segments we “double count”, and subtract that from the total number of points in R)