# Introduction

How do I compute with geometry?

Every Lecture: real life problem and model it in a mathematical way and solve it. 

**Example:** *post-office problem* Store the locations $P$ of post offices s.t. we can quickly find the post office closest to a query point $q$?

Solution:  	

1. Build a **Voronaoi diagram** op $P$
		  	
2. preprocess it for point locaton queries $O(\log n)$.

**Course site:** ics-websites.science.uu.nl/docs/vakken/gs/2024/. **Book:** computational geometry.

Mostly theory, not much implementation.

**Grading:** 

- 3 homework exams with problems you have to find an algorithm for and prove correctness and efficiency. Biggest part of the course. **First deadline:** vr 29 nov
- Final Exam at the end 45%
- Bonus assignment +0.5pt

**Today:**

- Different than normal lectures
- Basic concepts

# Geometry, points, lines, ...

- Plane $\mathbb{R}^2$
- Space $\mathbb{R}^3$ or $\mathbb{R}^d$

A **Line** in the plane: $y=m\cdot x + c$ representation by $m$ and $c$.

A **Half-plane** in the plane: $y\leq m\cdot x+c$ or $y\geq m\cdot x + c$

Represent vertical lines? Not by $m$ and $c$...

A **Line segment** $\overline{pq}$ is defined by its two endpoints $P$ and $q$:

$$\{\lambda p_x+(1-\lambda)\cdot q_x \mid \lambda\in [0,1]\}$$

Line segments are assumed to be **closed** = with endpoints, not **open**.

A **Polygon** is a connected region of the plane bounded by a sequence of lines segments

- Simpole polygon
- Polygon with holes
- Convex polygon

The lines segments o a polygon are called its **edgees**, the endpoints of tohose edges are the **vertices**

We don't count polygons where the edges intersect.

Some abuse: Polygon is only boundary, or interioir plus boundary.

A **circle** is only the boundary, a **disk** is the boundary plus the interior.

Rectangles, squares, quadrants, slabs, half-lines, wedges,...

# Relations: distance, intersection, angle

The distance between two points is generally the **Euclidean distance:**

Another is the **Manhatten distance:**

**Question:** Waht is the set of points at equal Manhatten distance to some point?:

**Answer:** Diamond

The distance between to geometric objects other than points usually refers to the minimum distance between two points that are part of these objects

**Question:** How can the distance between to line segments be realized?

**Answer:** If it intersects it is zero. Otherwise it is the distance between two endpoints or the distance between an endpoint and a perpendicular point of the other segment.

# Combinatorial complexity

A point in the plane can be represented using tow reals.

A line in the plance be reprsented using two reals and a bollean (for example)

A line segment can be represented by two points, so four reals

A circle (or disk) requires three reals to store it (Center, radius)

A rectangle requires four reals to store it.

They all take up constan size

A simple polygon int th plance be represented using $2n$ real if it has n4 vertices (and necessaryily, $n$ edges)

A set of $n$ points requires $2n$ reals

A set of $n$ line segments requires $4n$ reals

Any computation (distanc intersection) ont two objects of $O(1)$ description size takes $O(1)$ time!

**Question:** Supose that assimple polygon with $n$ vertices is given: the vertices are given in counterclockwise order along the boundary. Give an efficient algorithm to determine all edgesthat are intersected y a given line.

How efficient is your alg? Why is your alg efficient?

**Answer:** Just iterate $O(n)$. There is no better algorithm, because in the worst case we can have a polygon that intersects all lines, hence we need to check all of them.

Recall from your algorithms and data structures course:

A set of $n$ real numbers can be sorted in $O(n\log n)$ time

A set of $N$ real numbers can be stored in a data struture that uses $O(n)$ storage and that allows searching, insertion, and deletion in $O(\log n)$ time per operation.

# Convexity

A or set is **convex** iff any two points that are part of the shape, the whole conneting line segment is also part of the shape.

**Question:** which of the following shapes are convx? Point(yes), line(yes) sgement(yes), line(yes), circle(no), disk(yes), quadrant(yes)

For any subset $S$ of the plane (set of points, rectangle, simple polygon), its **convex hull** $\mathcal{C}\mathcal{H}(S)$ is the intersection of ll converx sets that contain S.

Intuitivly, the convex hull is the "smalles" set that contains $S$.

It is a lot more efficient to see if there is an intersection as there can only be two intersectionss.  


**Announcement:** Friday lectures are streamed because of the strike.

Assume the $n$ points are distinc.

The **ouput** has at least 4 and at most $2n$ coordinates, so it has size between $O(1)$ and $O(n)$. 

**Property:** The vertices of the convex hull are always points from the input.

Consequently, the edges of the convex hull connect wo points of the input.

You have to **prove** these properties.

**Property:** the supporting line o any convex hull edge has all input points to one side.

**An answer:** For every pair of points apply the last property and all the pairs that remain are the edges of the hull. 

**Idea:** Let us first compute the **Upper boundary** of the convex hull. Lower boundary is symmetric 

**Observation:** From left to right, there are only right turns on the upper turns

**Main idea:** Sort the points from left to right (== by $x$-coordinates)

- Initilize by adding the leftmost points
- Add the leftmost point.
- If you get a left-turn remove vertices in between, until you don't have left-turns

**Property:** On the upper hull, points appear in $x$-order

**Complexity:** $O(n\log n)$, because of the sorting and afterwards it takes $O(n)$ time, because every point is considered maximally twice.

**Other algs:** Divide and conquer, disjoint divide and conquer. There is an algorithm $n\log h$ where $h$ is the size of the hull. In 3d you can solve it in $n\log h$ and in $\mathbb{R}^d$ then you have $n^{\lfloor {\frac{d}{2}}\rfloor }$