Qhull options: Delauany and Voronoi

Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Qhull options

To: Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace

# Qhull options: Delaunay and Voronoi

This section lists the options for Delaunay triangulations, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams.

Qhull computes these structures as convex hulls. This may be confusing. To help you understand Qhull, each structure is introduced with a representative example. You can use the same options with your application. Experiment with the other options as you need them.

Copyright © 1995-1998 The Geometry Center, Minneapolis MN

## »Delaunay triangulation ('d')

The Delaunay triangulation is the triangulation with empty circumspheres. It has many useful properties and applications. See the survey article by Aurenhammer ['91] and the detailed introduction by O'Rourke ['94].

Example: rbox 10 D2 | qhull d QJ s i TO result
  Compute the 2-d Delaunay triangulation of 10 random points. Joggle the input to guarantee triangular output. Write a summary to the console and the triangles to 'result'.
Example: rbox r y c G0.1 D2 | qhull d Qbb s Fv TO result
  Compute the 2-d Delaunay triangulation of a triangle and a small square. Scale the paraboloid to the input points. Write a summary to the console and triangles to 'result'. Merge triangles for cocircular input sites (i.e., the square).

Qhull computes the Delaunay triangulation by computing a convex hull. It lifts the input sites to a paraboloid by adding the sum of the squares of the coordinates. It computes the convex hull of the lifted sites, and projects the lower convex hull to the input. Each triangle of the Delaunay triangulation corresponds to a facet of the lower half of the convex hull. Facets of the upper half of the convex hull correspond to the furthest-site Delaunay triangulation. See the examples, Delaunay and Voronoi diagrams.

See Qhull FAQ - Delaunay and Voronoi diagram questions.

Most users should use 'qhull d QJ' or 'qhull d Qbb'. If you use 'QJ', duplicate points will create small triangles. If you do not use 'QJ', the output reports duplicate input sites and merges facets for cocircular or cospherical input sites. See Joggled input or merged facets.

### »Delaunay conventions

The following terminology is used for Delaunay triangulations in Qhull for dimension d. The underlying structure is the lower facets of a convex hull in dimension d+1. For further information, see data structures and convex hull conventions.

- input site - a point in the input (one dimension lower than a point on the convex hull)
- point - a point has d+1 coordinates. The last coordinate is the sum of the squares of the input site's coordinates
- coplanar point - a nearly incident input site
- vertex - a point on the paraboloid. It corresponds to a unique input site.
- point-at-infinity - a point added above the paraboloid by option 'Qz'
- lower facet - a facet corresponding to a Delaunay triangle. The last coefficient of its normal is negative.
- upper facet - a facet corresponding to a furthest-site Delaunay triangle. The last coefficient of its normal is non-negative.
- Delaunay facet - a Delaunay triangle, i.e., a lower facet projected to the input sites
- upper Delaunay facet - an upper facet projected to the input sites
- non-simplicial facet - more than d input sites are cocircular or cospherical
- good facet - a Delaunay facet with optional restrictions by 'QVn', etc.

### »Delaunay outputs

These options control the output of Delaunay triangulations:

  General
FA
  compute total area for 's' and 'FS'
o
  print lower facets of the corresponding convex hull (a paraboloid)
s
  print summary for the Delaunay triangulation. Use 'Fs' for the numbers.
  Delaunay facets
i
  list input sites for each Delaunay facet. In 3-d and higher, report cospherical sites by adding extra points.
Fv
  list input sites for each Delaunay facet
Fn
  list neighboring facets for each Delaunay facet
FN
  list neighboring facets for each input site
Fa
  print area for each Delaunay facet
Ft
  print coordinates of the input sites and any added points. Then list the input sites for each Delaunay triangle. Added points occur for cospherical sites.
  Input sites
Fx
  list extreme points of the input sites
Qc Fc
  list nearly incident input sites for each Delaunay facet (one facet per input site). Do not use QJ.
Qc FP
  print nearly incident input sites with distance to nearest unique input site (i.e., vertex). Do not use QJ.

### »Delaunay controls

These options provide additional control:

Qz
  add a point above the paraboloid to reduce precision errors. Use it for nearly cocircular/cospherical input (e.g., 'rbox c | qhull d Qz'). The point is printed for options 'Ft' and 'o'.
PDk:1
  include upper and lower facets in the output (where k is the last dimension)
QJ
  joggle the input to avoid cospherical and nearly incident sites. Sets 'Qbb' to scale the paraboloid to the input.
f
  print the data structure for each facet
TFn
  report progress after constructing n facets
Qbb
  scale the paraboloid to reduce precision errors. Use it for integer coefficients and nearly cocircular/cospherical input.
QVn Pg
  select facets adjacent to input site n (marked 'good')
Tv
  verify result

### »Delaunay graphics

For 2-d and 3-d Delaunay triangulations, Geomview ('qhull d G') displays the corresponding convex hull (a paraboloid).

To view a 2-d Delaunay triangulation, use 'qhull d GrD2' to drop the last dimension. This is the same as viewing the hull without perspective (see Geomview's 'cameras' menu).

To view a 3-d Delaunay triangulation, use 'qhull d GrD3' to drop the last dimension. You may see extra edges. These are interior edges that Geomview moves towards the viewer (see 'lines closer' in Geomview's camera options). Use option 'Gt' to make the outer ridges transparent in 3-d. See Delaunay and Voronoi examples.

For 2-d Delaunay triangulations, Mathematica output ('m') displays the corresponding convex hull (a paraboloid).

### »Delaunay notes

A non-simplicial facet indicates nearly cocircular or cospherical input sites. To avoid non-simplicial facets joggle the input with 'QJ' or use option 'Ft' to print a triangulation. It adds points for non-simplicial facets. Alternatively, use an exact arithmetic code.

To compute the Delaunay triangulation of points on a sphere, compute their convex hull. If the sphere is the unit sphere at the origin, the facet normals are the Voronoi vertices of the input. The points may be restricted to a hemisphere. [S. Fortune]

The 3-d Delaunay triangulation of regular points on a half spiral (e.g., 'rbox 100 l | qhull d') has quadratic size, while the Delaunay triangulation of random 3-d points is approximately linear for reasonably sized point sets.

With the Qhull library, you can use qh_findbestfacet in `poly2.c` to locate the facet that contains a point. You should first lift the point to the paraboloid (i.e., the last coordinate is the sum of the squares of the point's coordinates -- qh_setdelaunay). Do not use options 'Qbb', 'QbB', 'Qbk:n', or 'QBk:n' since these scale the last coordinate.

If a point is interior to the convex hull of the input set, it is interior to the adjacent vertices of the Delaunay triangulation. This is demonstrated by the following pipe for point 0:

> qhull <data d s FQ QV0 Pg p | qhull s Qb3:0B3:0 p

The first call to Qhull returns the neighboring points of point 0 in the Delaunay triangulation. The second call to Qhull returns the vertices of the convex hull of these points (after dropping the lifted coordinate). If point 0 is interior to the original point set, it is interior to the reduced point set.

## »Voronoi diagram ('v')

The Voronoi diagram is the nearest-neighbor map for a set of points. It has many useful properties and applications. See the survey article by Aurenhammer ['91] and the detailed introduction by O'Rourke ['94]. The Voronoi diagram is the dual of the Delaunay triangulation.

Example: rbox 10 D3 | qhull v QJ s o TO result
  Compute the 3-d Voronoi diagram of 10 random points. Joggle the input to guarantee triangular output. Write a summary to the console and the Voronoi vertices and regions to 'result'. The first vertex of the result indicates unbounded regions.

Example: rbox r y c G0.1 D2 | qhull v Qbb s o TO result
  Compute the 2-d Voronoi diagram of a triangle and a small square. Scale the paraboloid to the input points. Write a summary to the console and Voronoi vertices and regions to 'result'. Report a single Voronoi vertex for cocircular input sites. The first vertex of the result indicates unbounded regions. The origin is the Voronoi vertex for the square.

Example: rbox r y c G0.1 D2 | qhull v Qbb Fv TO result
  Compute the 2-d Voronoi diagram of a triangle and a small square. Scale the paraboloid to the input points. Write a summary to the console and the Voronoi ridges to 'result'. Each ridge is the perpendicular bisector of a pair of input sites. Vertex "0" indicates unbounded ridges. Vertex "8" is the Voronoi vertex for the square.

Qhull computes the Voronoi diagram via the Delaunay triangulation ('d'). Each Voronoi vertex is the circumcenter of a facet of the Delaunay triangulation. Each Voronoi region corresponds to a vertex of the Delaunay triangulation (i.e., an input site).

Qhull outputs the Voronoi vertices for each Voronoi region (i.e., each input point). With option 'Fv'), it lists all ridges of the Voronoi diagram with the corresponding pair of input sites. You can also output a single Voronoi region for further processing [see graphics].

See Qhull FAQ - Delaunay and Voronoi diagram questions.

Most users should use 'qhull v QJ' or 'qhull v Qbb'. If you use 'QJ', duplicate points will create small triangles and cocircular or cospherical input sites create multiple Voronoi vertices. If you do not use 'QJ', the output reports duplicate input sites and reports one Voronoi vertex for cocircular or cospherical input sites. See Joggled input or merged facets'.

### »Voronoi conventions

The following terminology is used for Voronoi diagrams in Qhull. The underlying structure is a Delaunay triangulation from a convex hull in one higher dimension. Facets of the Delaunay triangulation correspond to vertices of the Voronoi diagram. Vertices of the Delaunay triangulation correspond to input sites. They also correspond to regions of the Voronoi diagram. See convex hull conventions and Delaunay conventions.

- input site - a point in the input (one dimension lower than a point on the convex hull)
- point - a point has d+1 coordinates. The last coordinate is the sum of the squares of the input site's coordinates
- coplanar point - a nearly incident input site
- vertex - a point on the paraboloid. It corresponds to a unique input site.
- point-at-infinity - a point added above the paraboloid by option 'Qz'
- Delaunay facet - a lower facet of the paraboloid. It is projected to the input sites
- Voronoi vertex - the circumcenter of a Delaunay facet
- Voronoi region - the Voronoi vertices for an input site. The region of Euclidean space nearest to an input site.
- Voronoi diagram - the graph of the Voronoi regions. It includes the ridges (i.e., edges) between the regions.
- infinity vertex - the Voronoi vertex that indicates unbounded Voronoi regions in 'o' output format. Its coordinates are -10.101.
- good facet - a Delaunay facet with optional restrictions by 'QVn', etc.

### » Voronoi outputs

These options control the output of Voronoi diagrams. Other output options return the corresponding Delaunay triangulation.

  General
s
  print summary of the Voronoi diagram. Use 'Fs' for the numbers.
  Voronoi vertices
Fv
  list ridges of Voronoi vertices for pairs of input sites.
Fn
  list the neighboring Voronoi vertices for each Voronoi vertex
FN
  list the Voronoi vertices for each Voronoi region
p
  print the coordinates of the Voronoi vertices.
FC
  print Voronoi vertex ("center") for each facet
  Voronoi regions
i
  list the Voronoi regions for each Voronoi vertex
o
  print coordinates of the Voronoi vertices and list the vertices for each input site. In 2-d, this is the Voronoi diagram without the unbounded rays.
Fi
  print separating hyperplanes for inner, bounded Voronoi regions
Fo
  print separating hyperplanes for outer, unbounded Voronoi regions
  Input sites
Fv
  list the adjacent input sites and the corresponding ridge of the Voronoi diagram.
Qc FP
  print nearly incident points with distance to nearest input site
QVn Pg
  select Voronoi vertices for input site n

For the 'o' option, the first number is the dimension. The next two numbers are the number of vertices and the number of input sites. The line ends with a "1". The Voronoi vertices are listed one per line. The first (0'th) vertex indicates the infinity vertex. Its coordinates are -10.101. The infinity vertex also occurs for degenerate Delaunay triangles.

The Voronoi regions follow the vertices with one line per input site. Each region is defined by the number of Voronoi vertices followed by the index of each vertex. Coplanar input sites have "0" vertices. In 2-d, the vertices are listed in adjacency order (unoriented). In 3-d and higher, the vertices are listed in numeric order. A zero index indicates the infinity vertex. Such regions are unbounded. If you use option 'Qz', the last line will be the Voronoi region for the point-at-infinity (a single "0").

For the 'Fv' option, the first line is the number of ridges. The remaining lines list the number of indices, a pair of input sites, and the corresponding ridge of the Voronoi diagram. Vertex 0 indicates an unbounded ray.

### » Voronoi controls

These options provide additional control:

Qz
  add a point above the paraboloid to reduce precision errors. Use it for nearly cocircular/cospherical input (e.g., 'rbox c | qhull v Qz').
QJ
  joggle the input and set 'Qbb'
f
  print the data structure for each facet
TFn
  report progress after constructing n facets
Qbb
  scale the last coordinate to reduce precision errors. Use it for integer coefficients and nearly cocircular/cospherical input.
Tv
  verify result

### » Voronoi graphics

In 2-d, Geomview output ('G') displays a Voronoi diagram with extra edges to close the unbounded Voronoi regions. To view the unbounded rays, enclose the input points in a square.

You can also view individual Voronoi regions in 3-d. To view the Voronoi region for site 3 in Geomview, execute

> qhull <data v 'QV3' 'p' 'Pg' | qhull s G >output

The first `qhull` command returns the Voronoi vertices for all facets incident to point 3 in the Delaunay triangulation. The second `qhull` command computes their convex hull. This is the Voronoi region for input site 3.

See the Delaunay and Voronoi examples for 2-d and 3-d examples. Turn off normalization (on Geomview's 'obscure' menu) when comparing the Voronoi diagram with the corresponding Delaunay triangulation.

### »Voronoi notes

You can simplify the Voronoi diagram by enclosing the input sites in a large square or cube.

See Voronoi graphics for computing the convex hull of a Voronoi region.

Unbounded regions can be confusing. For example, '`rbox c | qhull v Qz o`' produces the Voronoi regions for the vertices of a cube centered at the origin. All regions are unbounded. The output is

>     3
>     2 9 1
>     -10.101 -10.101 -10.101
>          0      0      0
>     2 0 1
>     2 0 1
>     2 0 1
>     2 0 1
>     2 0 1
>     2 0 1
>     2 0 1
>     2 0 1
>     0

The first line is the dimension. The second line is the number of vertices and the number of regions. There is one region per input point plus a region for the point-at-infinity added by option 'Qz'. The next two lines lists the Voronoi vertices. The first vertex is the infinity vertex. It is indicate by the coordinates -10.101. The second vertex is the origin. The next nine lines list the regions. Each region lists two vertices -- the infinity vertex and the origin. The last line is "0" because no region is associated with the point-at-infinity. A "0" would also be listed for nearly incident input sites.

To use option 'Fv', add an interior point. For example,

>     rbox c P0 | qhull v Fv
>     20
>     5 0 7 1 3 5
>     5 0 3 1 4 5
>     5 0 5 1 2 3
>     5 0 1 1 2 4
>     5 0 6 2 3 6
>     5 0 2 2 4 6
>     5 0 4 4 5 6
>     5 0 8 5 3 6
>     5 1 2 0 2 4
>     5 1 3 0 1 4
>     5 1 5 0 1 2
>     5 2 4 0 4 6
>     5 2 6 0 2 6
>     5 3 4 0 4 5
>     5 3 7 0 1 5
>     5 4 8 0 6 5
>     5 5 6 0 2 3
>     5 5 7 0 1 3
>     5 6 8 0 6 3
>     5 7 8 0 3 5

The output consists of 20 ridges and each ridge lists a pair of input sites and a triplet of Voronoi vertices. The first eight ridges connect the origin ('P0'). The remainder list the edges of the cube. Each edge generates an unbounded ray through the midpoint. The corresponding separating planes ('Fo') follow each pair of coordinate axes.

## »Furthest-site Delaunay triangulation ('d Qu')

The furthest-site Delaunay triangulation is dual of the furthest-site Voronoi diagram. It corresponds to the upper Delaunay facets of the Delaunay construction ('d').

Example: rbox 10 D2 | qhull d Qu QJ s i TO result
  Compute the 2-d, furthest-site Delaunay triangulation of 10 random points. Joggle the input to guarantee triangular output. Write a summary to the console and the triangles to 'result'.

Example: rbox r y c G1 D2 | qhull d Qu Qbb s Fv TO result
  Compute the 2-d furthest-site Delaunay triangulation of a square and a small triangle. Scale the paraboloid to the input points. Write a summary to the console and triangles to 'result'. Merge triangles for cocircular input sites. The square is the only furthest-site Delaunay triangle.

As in the Delaunay triangulation, Qhull computes the furthest-site triangulation by lifting the input sites to a paraboloid. The lower facets correspond to the Delaunay triangulation while the upper facets correspond to the furthest-site triangulation. Neither triangulation includes "vertical" facets (i.e., facets whose last hyperplane coefficient is nearly zero). Vertical facets correspond to input sites that are coplanar to the convex hull of the input. An example is points on the boundary of a lattice.

Most users should use 'qhull d Qu QJ' or 'qhull d Qu Qbb'. If you use 'QJ', duplicate points will create small triangles. If you do not use 'QJ', the output reports duplicate input sites and merges facets for cocircular or cospherical input sites. See Joggled input or merged facets'.

### »furthest-site Delaunay conventions

The following terminology is used for furthest-site Delaunay triangulations in Qhull. The underlying structure is the upper facets of a convex hull in one higher dimension. See convex hull conventions and Delaunay conventions.

- input site - a point in the input (one dimension lower than a point on the convex hull)
- point - d+1 coordinates. The last coordinate is the sum of the squares of the input site's coordinates
- coplanar point - a nearly incident input site
- vertex - a point on the paraboloid. It corresponds to a unique input site.
- upper facet - a facet with a positive last coefficient for the hyperplane
- upper Delaunay facet - an upper facet projected to the input sites
- non-simplicial facet - more than d points are cocircular or cospherical
- good facet - a Delaunay facet with optional restrictions by 'QVn', etc.

### »furthest-site Delaunay outputs

These options control the output of furthest-site Delaunay triangulations:

  General
FA
  compute total area for 's' and 'FS'
o
  print upper facets of the corresponding convex hull
s
  print summary for the furthest-site Delaunay triangulation. Use 'Fs' for the numbers.
  furthest-site Delaunay facets
i
  list the input sites for each furthest-site Delaunay facet
Fv
  list input sites for each furthest-site Delaunay facet
FN
  list neighboring facets for each input site
Fn
  list neighboring facets for each furthest-site Delaunay facet
Fa
  print area for each furthest-site Delaunay facet
Ft
  print coordinates of the input sites and any added points. Then list the input sites for each furthest-site Delaunay triangle
  Input sites
Fx
  list extreme points of the input sites

### »furthest-site Delaunay controls

These options provide additional control:

PDk:1
  include upper and lower facets in the output (k is the last dimension)
QJ
  joggle the input and set 'Qbb'
f
  print the data structure for each facet
TFn
  report progress after constructing n facets
Qbb
  scale the last coordinate to reduce precision errors. Use it for integer coefficients and nearly cocircular/cospherical input.
QVn Pg
  select facets adjacent to input site n (marked 'good')
Qg
  skip input sites that can not effect the result.
Tv
  verify result

### »furthest-site Delaunay graphics

For 2-d and 3-d furthest-site Delaunay triangulations, Geomview ('qhull d Qu G') displays the corresponding convex hull (a paraboloid).

To get a 2-d furthest-site Delaunay triangulation, use 'qhull d Qu GrD2' to drop the last dimension. This is the same as viewing the hull without perspective (see Geomview's 'cameras' menu).

To get a 3-d furthest-site Delaunay triangulation, use 'qhull d Qu GrD3' to drop the last dimension. You may see extra edges. These are interior edges that Geomview moves towards the viewer (see 'lines closer' in Geomview's camera options). Use option 'Gt' to make the outer ridges transparent in 3-d.

For 2-d furthest-site Delaunay triangulations, Mathematica ('m') displays the corresponding convex hull (a paraboloid).

### »furthest-site Delaunay notes

See Delaunay notes.

## »Furthest-site Voronoi diagram ('v Qu')

The furthest-site Voronoi diagram is the furthest-neighbor map for a set of points. See the survey article by Aurenhammer ['91] and a brief introduction by O'Rourke ['94].

Example: rbox 10 D2 | qhull v Qu QJ s o TO result
  Compute the 2-d, furthest-site Voronoi diagram of 10 random points. Joggle the input to guarantee triangular output. Write a summary to the console and the Voronoi regions and vertices to 'result'. The first vertex of the result indicates unbounded regions. Almost all regions are unbounded.

Example: rbox r y c G1 D2 | qhull d Qu Qbb s o TO result
  Compute the 2-d furthest-site Voronoi diagram of a square and a small triangle. Scale the paraboloid to the input points. Write a summary to the console and the Voronoi regions and vertices to 'result'. Report a single furthest-site Voronoi vertex for cocircular input sites. The origin is the furthest-site Voronoi vertex of the square.

The furthest-site Voronoi diagram is the dual of the furthest-site Delaunay triangulation. Each furthest-site Voronoi vertex is the circumcenter of an upper facet of the Delaunay triangulation. Each furthest-site Voronoi region corresponds to a vertex of the Delaunay triangulation (i.e., an input site). The correspondence skips interior input sites.

Qhull outputs the furthest-site Voronoi vertices for each furthest-site Voronoi region, and the ridge of the furthest-site Voronoi diagram for each corresponding pair of input sites on the convex hull.

Most users should use 'qhull v Qu QJ' or 'qhull v Qu Qbb'. If you use 'QJ', duplicate points will create small triangles. If you do not use 'QJ', the output reports duplicate input sites and merges facets for cocircular or cospherical input sites. See Joggled input or merged facets'.

### » furthest-site Voronoi conventions

The following terminology is used for furthest-site Voronoi diagrams in Qhull. The underlying structure is a furthest-site Delaunay triangulation from a convex hull in one higher dimension. Upper facets of the Delaunay triangulation correspond to vertices of the furthest-site Voronoi diagram. Vertices of the furthest-site Delaunay triangulation correspond to input sites. They also define regions of the furthest-site Voronoi diagram. All vertices are extreme points of the input sites. See convex hull conventions and furthest-site Delaunay conventions.

- input site - a point in the input (one dimension lower than a point on the convex hull)
- point - a point has d+1 coordinates. The last coordinate is the sum of the squares of the input site's coordinates
- coplanar point - a nearly incident input site
- vertex - a point on the upper facets of the paraboloid. It corresponds to a unique input site.
- furthest-site Voronoi vertex - the circumcenter of a furthest-site Delaunay facet
- furthest-site Voronoi region - the region of Euclidean space further from an input site than any other input site. Qhull lists the furthest-site Voronoi vertices that define each furthest-site Voronoi region.
- furthest-site Voronoi diagram - the graph of the furthest-site Voronoi regions with the ridges (edges) between the regions.
- infinity vertex - the Voronoi vertex for unbounded furthest-site Voronoi regions in 'o' output format. Its coordinates are -10.101.
- good facet - an upper Delaunay facet with optional restrictions by 'QVn', etc.

### »furthest-site Voronoi outputs

These options control the output of furthest-site Voronoi diagram. Other output options return the corresponding furthest-site Delaunay triangulation.

  General
s
  print summary for the furthest-site Voronoi diagram. Use 'Fs' for the numbers.
QVn Pg
  select furthest-site Voronoi vertices for input site n
  furthest-site Voronoi vertices
Fn
  list neighboring furthest-site Voronoi vertices for each furthest-site Voronoi vertex
Fv
  list ridges of Voronoi vertices for pairs of input sites.
p
  print coordinates of the furthest-site Voronoi vertices.
FC
  print Voronoi vertex ("center") for each facet
  furthest-site Voronoi regions
i
  list furthest-site Voronoi regions for each furthest-site Voronoi vertex
FN
  list furthest-site Voronoi vertices for each furthest-site Voronoi region
o
  print coordinates of the furthest-site Voronoi vertices and list the furthest-site Voronoi vertices for each input site.
Fi
  print separating hyperplanes for inner, bounded Voronoi regions
Fo
  print separating hyperplanes for outer, unbounded Voronoi regions

For the 'o' option, the first number is the dimension. The next two numbers are the number of vertices and the number of input sites. The line ends with a "1". The furthest-site Voronoi vertices are listed one per line. The first (0'th) vertex indicates the infinity vertex. Its coordinates are -10.101. The infinity vertex also occurs for degenerate Delaunay triangles.

The furthest-site Voronoi regions follow the vertices with one line per input site. Each region is defined by the number of furthest-site Voronoi vertices followed by the index of each vertex. Coplanar and interior input sites have "0" vertices. In 2-d, the vertices are listed in adjacency order (unoriented). In 3-d and higher, the vertices are listed in numeric order. A zero index indicates the infinity vertex. Such regions are unbounded.

For the 'Fv' option, the first line is the number of ridges. The remaining lines list the number of indices, a pair of input sites, and the corresponding ridge of the furthest-site Voronoi diagram. Vertex 0 indicates an unbounded ray.

### »furthest-site Voronoi controls

These options provide additional control:

QJ
  joggle the input and set 'Qbb'
f
  print the data structure for each facet
TFn
  report progress after constructing n facets
Qbb
  scale the last coordinate to reduce precision errors. Use it for integer coefficients and nearly cocircular/cospherical input.
Qg
  skip input sites that can not effect the result.
Tv
  verify result

### »furthest-site Voronoi graphics

In 2-d, Geomview output ('G') displays a furthest-site Voronoi diagram with extra edges to close the unbounded furthest-site Voronoi regions. All regions will be unbounded.

See the Delaunay and Voronoi examples for a 2-d example. Turn off normalization (on Geomview's 'obscure' menu) when comparing the furthest-site Voronoi diagram with the corresponding Voronoi diagram.

### »furthest-site Voronoi notes

See Voronoi notes.

Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Qhull options

To: Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace

The Geometry Center Home Page

Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top