URG - K2

## Kolokvij

### Delaunay Triangulation

 - Gift Wrapping
 - Incremental Algorithms
    - Big Triangle
    - In what triangle is the point?
        - GKS - Guibas, Knuth and Sharir
            - Hierarchial Structure
            - DAG
        - Randomization + A* star walking
 - Divide & Conquer
    - De Wall
 - Sweep Line
    - Auxiliary Line
    - Advancing Front
 - High Dimensional Embedding
    - z = x^2 + y^2
    - Convex Hull
    - Project

 > N - points
 > K - points on the Convex Hull
 > |Triangles| = 2*N - 2 - K
 > |Edges| = 3*N - 3 - K
 > Delaunay Triangulation can have at most 2*n - 5 triangles
 > Thales Theorem to prove edge flips
 > Legal Triangulation <=> Delaunay Triangulation
 > Legal Triangulation is UNIQUE
 > In non general position, not every Delaunay Triangulation is Angle Optimal
 > The Euclidean minimum spanning tree is a subset of Delaunay edges.

### Voronoi Diagram

Definition: Voronoi Cell of point[i] is the polygon represented by the intersection of
halfplanes constructed by the bisectors of point[i] and point[j] for every other `j` except `i`.

 - Naive Method
    O(n * n^2)
    for each point O(n)
        get all bisectors O(n)
        for i in bisectors
            for j in bisectors
                get intersection point
                constructing a cell

 - Incremental Method
 - Divide and Conquer
 - Sweep line

 > Voronoi Cells are Convex


### Angle Optimal Triangulations

 - Angle Vector = (a_1, a_2, a_3 ...)
 - Optimal = lexicographically largest
 - Local edge flips improve the optimal angle triangulation

### Polygons

Classification of polygons:
 - simple
    - no intersections of edges
    - each vertex has exactly 2 edges
 - not-simple

 - convex
 - non-convex

 - monotonic
 - non-monotonic

 > Monotonic Chain
 > Holes on the odd and even levels are oriented differently

Algorithms for checking if a point is inside a polygon

Without preprocessing:
 - Sign method (convex) O(N)
    - all signs of cross products have to be equal
 - Halftrack method (metoda poltraka) O(N)
    -
 - Vsota kotov O(N)
    - 360 deg - inside
    -   0 deg - outside
 - KKS Method O(N)
    -  per query

With preprocessing:
 - Metoda s klini (convex)
    - preprocessing: O(N log N)
    - query: O(log N)
    - Binary search on which radar sector is the point located
    - Test if the point is inside or outside