---
tags: vaje, rg, konveksnost
hackmd: https://hackmd.io/DXPo1I1jR96lDAS69KMQUg
plugins: mathjax
---
# Computational geometry - Tutorial 14.4.2021

---

## Convexity

### Exercise 1

We are given a set of $10$ points ${\mathcal P} = \lbrace a, b, \dots, j \rbrace$. For the incremental algorithm and Graham's algorithm, specify the triples of points $(X, Y, Z) \in {\mathcal P}^3$ for which the algorithms checks whether the sequence $X,Y,Z$ is a right turn. The triples should be listed in the same order in which the algorithm considers them.



----


---

### Exercise 2

For a general $n$, describe a set $P$ of $n$ points in which at least one point occurs in $\Omega(n)$ triples when computing the convex hull of $P$ using the incremental algorithm.

----

Let $P$ be a set of points lying on the graph of a convex function. Then the leftmost point of $P$ will occur in $n-2$ triples when computing the upper hull. Therefore, it occurs in $\Omega(n)$ triples when using the incremental algorithm.


---

### Exercise 3

Graham's algorithm consists of two steps:
(1) we first build a polygon $M$ from the given points, and then (2) we change $M$ until we get $\operatorname{CH}(P)$. Show that step (2) is not sufficient to compute the convex hull of a polygon: find a polygon $N$ such that immediately performing step (2) on it does not yield $\operatorname{CH}(N)$.

----


---

### Exercise 4

Let $P$ be a set of points in the plane. For each point $p \in P$ we define

$$
\operatorname{cell}(p)=\{ x\in \mathbb{R}^2 \mid d(x,p)\leq d(x,p') \text{ for each }p'\in P\},
$$

where $d(\cdot, \cdot)$ is the Euclidean distance. Show that $\operatorname{cell}(p)$ is a convex set for each point $p \in P$.

----

$$
\operatorname{cell}(p) = \bigcap_{p' \in P} \{x \in \mathbb{R}^2 \mid d(x, p) \le d(x, p') \}
$$

$\operatorname{cell}(p)$ is an intersection of convex sets and is therefore itself convex.


---

### Exercise 5

A convex polygon $M$ is given as a list of vertices in clockwise order. Describe a linear time algorithm which sorts the vertices of the polygon $M$ by their $x$ coordinates. Can your algorithm be adapted so that it will work for any polygon $M$ (still in linear time)?

---


* Find the leftmost and rightmost vertex and identify the upper and lower paths
* Each path is a sorted list (by $x$), and we can merge them in linear time


For general polygons, we prove that a linear time algorithm would imply an $o(n \log n)$ time sorting algorithm.
* Input: list ${x_1}, {x_2}, \dots, {x_n}$
* Objective: return a sorted list
* Set ${x_0} = {x_{n+1}} = {\min_{i=1}^n} {x_i} - 1$
* Map ${x_i} \to {p_i} = ({x_i}, i)$ ($O(n)$)
* Run our algorithm with ${p_0}, {p_1}, \dots {p_{n+1}}$ ($O(n)$)
* Return the $x$ coordinates of the output (without the first two elements) ($O(n)$)
* Time complexity: $O(n)$

Clearly, such an algorithm will take $\Omega(n \log n)$ time!