* POLYTOPE

def: CH of finite set of points P
hyperplane: ax+b=0   half-space h-:ax+b<=0, h+:ax+b>=0
supporting hyperplane: intersects h, included in h+ or h-
face=intersection with a supporting hyperplane
faces are polytopes. faces are CH of subset -> finite number
polytope <=> bounded intersection of a finite number of half-spaces
convex polyhedron: intersection of a finite number of half-spaces, can be infinite
general position for points in R^d: every subset of <=d+1 points are affinely independent
 => faces are simplices, "simplicial polytope". boundary complex is a geometric simplicial complex
general position for hyperplanes in R^d: any k intersect in affine subspace of dim d-k. "simple convex polyhedron"
cell complex: set C of convex polyhedra (faces), face of face is a face, intersection of faces empty or common face
boundary complex is a cell complex
thm de la borne supérieure, borne inf
borne inf: (t,t²...t^2d), t1...td, prod(X-ti)²≥0, X^i->x_i et c'est l'équation d'un hyperplan support
algos enveloppe convexe dD

def voronoi
def delaunay
max complexité (3D: n²), borne inf de CH encore valide
Delaunay maximizes min angle, minimizes max min enclosing ball of simplices
Delaunay is a 1.99-spanner
premiers algos de reconstruction
Delaunay restreint
Crust
 2d: Delaunay of points and Voronoi vertices
 axe médian, reach
 pole of s: furthest point p+ in the voronoi cell (or average of normals to adjacent faces if on the convex hull), and the furthest point p- with negative projection on sp+.
 delaunay of points and poles
 remove poles and cofaces
 remove triangles when normal and sp+ make a large angle
 orient (inside/outside) consistently and extract manifold, avoiding sharp edges
Cocone
 sp+: estimated normal
 complement of cone of angle pi/2-theta
 keep Delaunay triangle if dual Voronoi edge intersects all 3 cocones (approx restricted Delaunay)
 same last extraction step as crust
(meshing: move points (or add weight) to avoid slivers)
Flow complex (partition by following the gradient of the distance)
alpha-shape (molécule d'eau)
alpha-complex (+ petit que Cech)

Algo (2D) pratique: localisation par marche + insertion.
 analyse backwards de l'insertion (dans un ordre aléatoire)
 différents types de marche (certaines ne marchent que pour Delaunay)
 marche: sqrt(n)*dist pour aléatoire
 tri space filling curve
 parabole -> quadratique
 BRIO