Reducing the degree of Apollonius Diagram Predicates David Millman

Reducing the degree of Apollonius Diagram Predicates

• David Millman

• Advisors: Sylvain Pion and Christophe Delage

• July 6th 2006

Background

• Voronoi Diagram

• Apollonius Diagram

• Power Diagram

• Incremental Algorithm

• Invert and project

Voronoi Diagram

Apollonius Diagram

• Weighed point or Site si is defined by pi, the point and wi the weight

Apollonius Graph

• Dual of Apollonius Diagram

• Vertex is a Site

• Edge two sites whose AW-Voronoi Cell share a face

Power Diagram

Incremental Algorithm

• The Three basic steps

• Locate nearest neighbor

• Check if new site is trivial

• Update

• Vertex Conflict
• Edge Conflict

Vertex Conflict

Edge Conflict

Invert and Project

Invert and Project

Invert and Project Convex Hull

Predicates

• Predicates

• Vertex Conflict, Edge Conflict

• Sub Predicates

• Orientation, Radical Side, Radical Intersection, Power Test, Order On a Line

Orientation

Radical Side

Radical Intersection

Vertex Conflict (revisited)

• There are 6 cases, and we have vertex conflict when:

Vertex Conflict (degeneracies)

• When Orientation is 0

• When Radical Intersection is 0

Pertubations

• Consistent ordering

• Max Radius

• Lexigraphically

Edge Conflict (revisited)

• We are looking for the case of q breaking 2 into multiple sections, when inverted and projection onto the unit sphere.

Numerical Results

• 66% speedup for vertex conflict 4 finite sites

• 39% speedup for vertex conflict 3 finite and 1 infinite site

• 10-20% less
  filter failures in nearly degenerate cases

Further Work

• Optimize Edge Conflict

• Optimizations of the Incremental Algorithm

• Degeneracies in 3D

• Reduction of Exact Computations

Reducing the degree of Apollonius Diagram Predicates