qdelaunay Qu -- furthest-site Delaunay triangulation

The furthest-site Delaunay triangulation corresponds to the upper facets of the Delaunay construction. Its vertices are the extreme points of the input sites. It is the dual of the furthest-site Voronoi diagram.

Example: rbox 10 D2 | qdelaunay Qu Qt s i TO result

Compute the 2-d, furthest-site Delaunay triangulation of 10 random points. Triangulate the output. Write a summary to the console and the regions to 'result'.

 

Example: rbox 10 D2 | qdelaunay 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 regions to 'result'.

 

Example: rbox r y c G1 D2 | qdelaunay Qu s Fv TO result

Compute the 2-d, furthest-site Delaunay triangulation of a triangle inside a square. Write a summary to the console and unoriented regions to 'result'. Merge regions for cocircular input sites (e.g., the square). The square is the only furthest-site Delaunay region.

As with the Delaunay triangulation, Qhull computes the furthest-site Delaunay 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.

By default, qdelaunay merges cocircular and cospherical regions. For example, the furthest-site Delaunay triangulation of a square inside a diamond ('rbox D2 c d G4 | qdelaunay Qu') consists of one region (the diamond).

If you use 'Qt' (triangulated output), all furthest-site Delaunay regions will be simplicial (e.g., triangles in 2-d). Some regions may be degenerate and have zero area.

If you use 'QJ' (joggled input), all furthest-site Delaunay regions will be simplicial (e.g., triangles in 2-d). Joggled input is less accurate than triangulated output ('Qt'). See Merged facets or joggled input.

The output for 3-d, furthest-site Delaunay triangulations may be confusing if the input contains cospherical data. See the FAQ item Why are there extra points in a 4-d or higher convex hull? Avoid these problems with triangulated output ('Qt') or joggled input ('QJ').

The 'qdelaunay' program is equivalent to 'qhull d Qbb'. It disables the following Qhull options: d n v H U Qb QB Qc Qf Qg Qi Qm Qr Qv Qx TR E V FC Fi Fo Fp Ft FV Q0,etc.

Copyright © 1995-2020 C.B. Barber

»furthest-site qdelaunay synopsis

See qdelaunay synopsis. The same program is used for both constructions. Use option 'Qu' for furthest-site Delaunay triangulations.

»furthest-site qdelaunay input

The input data on stdin consists of:

• dimension
• number of points
• point coordinates

Use I/O redirection (e.g., qdelaunay Qu < data.txt), a pipe (e.g., rbox 10 | qdelaunay Qu), or the 'TI' option (e.g., qdelaunay Qu TI data.txt).

For example, this is a square containing four random points. Its furthest-site Delaunay triangulation contains one square.

rbox c 4 D2 > data

2 RBOX c 4 D2
8
-0.4999921736307369 -0.3684622117955817
0.2556053225468894 -0.0413498678629751
0.0327672376602583 -0.2810408135699488
-0.452955383763607 0.17886471718444
  -0.5   -0.5
  -0.5    0.5
   0.5   -0.5
   0.5    0.5

qdelaunay Qu i < data

Furthest-site Delaunay triangulation by the convex hull of 8 points in 3-d:

  Number of input sites: 8
  Number of Delaunay regions: 1
  Number of non-simplicial Delaunay regions: 1

Statistics for: RBOX c 4 D2 | QDELAUNAY s Qu i

  Number of points processed: 8
  Number of hyperplanes created: 20
  Number of facets in hull: 11
  Number of distance tests for qhull: 34
  Number of merged facets: 1
  Number of distance tests for merging: 107
  CPU seconds to compute hull (after input): 0.02

1
7 6 4 5

»furthest-site qdelaunay outputs

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

furthest-site Delaunay regions

i

list input sites for each furthest-site Delaunay region. The first line is the number of regions. The remaining lines list the input sites for each region. The regions are oriented. In 3-d and higher, report cospherical sites by adding extra points. For the points-in-square example, the square is the only furthest-site Delaunay region.

Fv

list input sites for each furthest-site Delaunay region. The first line is the number of regions. Each remaining line starts with the number of input sites. The regions are unoriented. For the points-in-square example, the square is the only furthest-site Delaunay region.

Ft

print a triangulation of the furthest-site Delaunay regions in OFF format. The first line is the dimension. The second line is the number of input sites and added points, followed by the number of simplices and the number of ridges. The input coordinates are next, followed by the centrum coordinates. There is one centrum for each non-simplicial furthest-site Delaunay region. Each remaining line starts with dimension+1. The simplices are oriented. For the points-in-square example, the square has a centrum at the origin. It splits the square into four triangular regions.

Fn

list neighboring regions for each furthest-site Delaunay region. The first line is the number of regions. Each remaining line starts with the number of neighboring regions. Negative indices (e.g., -1) indicate regions outside of the furthest-site Delaunay triangulation. For the points-in-square example, the four neighboring regions are outside of the triangulation. They belong to the regular Delaunay triangulation.

FN

list the furthest-site Delaunay regions for each input site. The first line is the total number of input sites. Each remaining line starts with the number of furthest-site Delaunay regions. Negative indices (e.g., -1) indicate regions outside of the furthest-site Delaunay triangulation. For the points-in-square example, the four random points belong to no region while the square's vertices belong to region 0 and three regions outside of the furthest-site Delaunay triangulation.

Fa

print area for each furthest-site Delaunay region. The first line is the number of regions. The areas follow, one line per region. For the points-in-square example, the square has unit area.

 

 

Input sites

Fx

list extreme points of the input sites. These points are vertices of the furthest-point Delaunay triangulation. They are on the boundary of the convex hull. The first line is the number of extreme points. Each point is listed, one per line. The points-in-square example has four extreme points.

 

 

General

FA

compute total area for 's' and 'FS'. This is the same as the area of the convex hull.

o

print upper facets of the corresponding convex hull (a paraboloid)

m

Mathematica output for the upper facets of the paraboloid (2-d triangulations).

FM

Maple output for the upper facets of the paraboloid (2-d triangulations).

G

Geomview output for the paraboloid (2-d or 3-d triangulations).

s

print summary for the furthest-site Delaunay triangulation. Use 'Fs' and 'FS' for numeric data.

»furthest-site qdelaunay controls

These options provide additional control:

Qu

must be used for furthest-site Delaunay triangulation.

Qt

triangulated output. Qhull triangulates non-simplicial facets. It may produce degenerate facets of zero area.

QJ

joggle the input to avoid cospherical and coincident sites. It is less accurate than triangulated output ('Qt').

QRn

randomly rotate the input with a random seed of n. If n=0, the seed is the time. If n=-1, use time for the random seed, but do not rotate the input.

QVn

select facets adjacent to input site n (marked 'good').

Tv

verify result.

TI file

input data from file. The filename may not use spaces or quotes.

TO file

output results to file. Use single quotes if the filename contains spaces (e.g., TO 'file with spaces.txt'

TFn

report progress after constructing n facets

PDk:1

include upper and lower facets in the output. Set k to the last dimension (e.g., 'PD2:1' for 2-d inputs).

f

facet dump. Print the data structure for each facet (i.e., furthest-site Delaunay region).

»furthest-site qdelaunay graphics

See Delaunay graphics. They are the same except for Mathematica and Maple output.

»furthest-site qdelaunay notes

The furthest-site Delaunay triangulation does not record coincident input sites. Use qdelaunay instead.

qdelaunay Qu does not work for purely cocircular or cospherical points (e.g., rbox c | qdelaunay Qu). Instead, use qdelaunay Qz -- when all points are vertices of the convex hull of the input sites, the Delaunay triangulation is the same as the furthest-site Delaunay triangulation.

A non-simplicial, furthest-site Delaunay region indicates nearly cocircular or cospherical input sites. To avoid non-simplicial regions triangulate the output ('Qt') or joggle the input ('QJ'). Joggled input is less accurate than triangulated output. You may also triangulate non-simplicial regions with option 'Ft'. It adds the centrum to non-simplicial regions. Alternatively, use an exact arithmetic code.

Furthest-site Delaunay triangulations do not include facets that are coplanar with the convex hull of the input sites. A facet is coplanar if the last coefficient of its normal is nearly zero (see qh_ZEROdelaunay).

»furthest-site qdelaunay 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, Delaunay conventions, and Qhull's data structures

• 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
• vertex - a point on the paraboloid. It corresponds to a unique input site.
• furthest-site Delaunay facet - an upper facet of the paraboloid. The last coefficient of its normal is clearly positive.
• furthest-site Delaunay region - a furthest-site Delaunay facet projected to the input sites
• non-simplicial facet - more than d points are cocircular or cospherical
• good facet - a furthest-site Delaunay facet with optional restrictions by 'QVn', etc.

»furthest-site qdelaunay options

See qdelaunay options. The same program is used for both constructions. Use option 'Qu' for furthest-site Delaunay triangulations.

Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
To: synopsis • input • outputs • controls • graphics • notes • conventions • options

The Geometry Center Home Page

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