# HGeometry

## What is Computational Geometry?

Richard Feynman, a physicist and Nobel laureate, famously asked for a "map of the cat." He was attending a biology class at a whim and need information about a cat's anatomy but didn't know any of the terminology. Well, this page is a map of computational geometry.

To keep the number of algorithms managable, foundational concepts are favoured over heuristics. The cross or checkmark indicate whether the algorithm has been implemented in HGeometry.

## Random Polygon Generation

Random Convex Polygon
$$O(n \log n)$$
Random Monotone Polygon
$$O(n \log n)$$
Random Star-shaped Polygon
$$O(n \log n)$$
2-Opt Moves
$$O(?)$$
Random Growth
$$O(?)$$
Skeleton holes
$$O(?)$$

## 2D Interpolation

Linear
$$O(n)$$
?
Angular
$$O(?)$$
?
Edge+angle
$$O(?)$$
?
Least-work
$$O(?)$$
?
Star-skeleton
$$O(?)$$
?
As-rigid-as-possible
$$O(?)$$
?
Guaranteed intersection-free
$$O(?)$$
?

## Visibility

Linear Visibility
$$O(n)$$
Naive Visibility
$$O(n^2)$$

Wikipedia article: Visibility polygon

Sweep Visibility
$$O(n \log n)$$
Output-sensitive visibility
$$O(k)$$
$$O(n)$$
Visibility window
$$O(n)$$
Single-source shortest path
$$O(n)$$
Shortest path
$$O(n \log n)$$

## Convex related

Polygon Kernel
$$O(n)$$
Polygon Convex Hull
$$O(n)$$
Point Set Convex Hull
$$O(n \log n)$$
Convex point locator
$$O(\log n)$$
Convex extremes
$$O(\log n)$$
Convex Minkowski sum
$$O(n + m)$$
Convex intersection
$$O(\log n + \log m)$$
Optimal Convex Decomposition
$$O(nr^2)$$
ACD Lien/Amato
$$O(nr)$$
ACD Hertel/Mehlhorn
$$O(n)$$

## Triangulation

Triangulation with holes
$$O(n \log n)$$
Triangulation without holes
$$O(n \log^\star n)$$
Linear Triangulation without holes
$$O(n)$$
Constrained Delaunay Triangulation
$$O(n^2)$$
Constrained Delaunay Triangulation
$$O(n\log n)$$
Delaunay Triangulation
$$O(n \log n)$$
Compatible triangulation
$$O(?)$$

## Uncategorized

Segment intersections
$$O((n+k)\log n)$$

Wikipedia article: Bentley–Ottmann algorithm

Segment intersections
$$O(n\log n+k)$$
Douglas Peucker's simplification
$$O(n)$$
Euclidean Minimum Spanning Tree
$$O(n \log n)$$
2D closest pair
$$O(n \log n)$$
Polygon point locator
$$O(n)$$
Planar point location
$$O(\log n)$$
Boolean operations
$$O(nm)$$
Boolean operations
$$O((n+k) \log n)$$