1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<title>qvoronoi Qu -- furthest-site Voronoi diagram</title>
</head>
<body>
<!-- Navigation links -->
<a name="TOP"><b>Up</b></a><b>:</b>
<a href="http://www.qhull.org">Home page</a> for Qhull<br>
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
• <a href="qh-quick.htm#options">Options</a>
• <a href="qh-opto.htm#output">Output</a>
• <a href="qh-optf.htm#format">Formats</a>
• <a href="qh-optg.htm#geomview">Geomview</a>
• <a href="qh-optp.htm#print">Print</a>
• <a href="qh-optq.htm#qhull">Qhull</a>
• <a href="qh-optc.htm#prec">Precision</a>
• <a href="qh-optt.htm#trace">Trace</a>
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
<b>To:</b> <a href="#synopsis">sy</a>nopsis
• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs
• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics
• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions
• <a href="#options">op</a>tions
<hr>
<!-- Main text of document -->
<h1><a
href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/delaunay.html"><img
src="qh--dt.gif" alt="[delaunay]" align="middle" width="100"
height="100"></a>qvoronoi Qu -- furthest-site Voronoi diagram</h1>
<p>The furthest-site Voronoi diagram is the furthest-neighbor map for a set of
points. Each region contains those points that are further
from one input site than any other input site. See the
survey article by Aurenhammer [<a href="index.htm#aure91">'91</a>]
and the brief introduction by O'Rourke [<a
href="index.htm#orou94">'94</a>]. The furthest-site Voronoi diagram is the dual of the <a
href="qdelau_f.htm">furthest-site Delaunay triangulation</a>.
</p>
<blockquote>
<dl>
<dt><b>Example:</b> rbox 10 D2 | qvoronoi <a
href="qh-optq.htm#Qu">Qu</a> <a href="qh-opto.htm#s">s</a>
<a href="qh-opto.htm#o">o</a> <a href="qh-optt.htm#TO">TO
result</a></dt>
<dd>Compute the 2-d, furthest-site Voronoi diagram of 10
random points. 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.</dd>
</dl>
<dl>
<dt><b>Example:</b> rbox r y c G1 D2 | qvoronoi <a
href="qh-optq.htm#Qu">Qu</a>
<a href="qh-opto.htm#s">s</a>
<a href="qh-optf.htm#Fn">Fn</a> <a href="qh-optt.htm#TO">TO
result</a></dt>
<dd>Compute the 2-d furthest-site Voronoi diagram of a square
and a small triangle. Write a summary to the console and the Voronoi
vertices for each input site to 'result'.
The origin is the only furthest-site Voronoi vertex. The
negative indices indicate vertices-at-infinity.</dd>
</dl>
</blockquote>
<p>
Qhull computes the furthest-site Voronoi diagram via the <a href="qdelau_f.htm">
furthest-site Delaunay triangulation</a>.
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).</p>
<p>See <a href="http://www.qhull.org/html/qh-faq.htm#TOC">Qhull FAQ</a> - Delaunay and
Voronoi diagram questions.</p>
<p>The 'qvonoroi' program is equivalent to
'<a href=qhull.htm#outputs>qhull v</a> <a href=qh-optq.htm#Qbb>Qbb</a>' in 2-d to 3-d, and
'<a href=qhull.htm#outputs>qhull v</a> <a href=qh-optq.htm#Qbb>Qbb</a> <a href=qh-optq.htm#Qx>Qx</a>'
in 4-d and higher. It disables the following Qhull
<a href=qh-quick.htm#options>options</a>: <i>d n m v H U Qb
QB Qc Qf Qg Qi Qm Qr QR Qv Qx TR E V Fa FA FC Fp FS Ft FV Gt Q0,etc</i>.
<p><b>Copyright © 1995-2015 C.B. Barber</b></p>
<hr>
<h3><a href="#TOP">»</a><a name="synopsis">furthest-site qvoronoi synopsis</a></h3>
<blockquote>
See <a href="qvoronoi.htm#synopsis">qvoronoi synopsis</a>. The same
program is used for both constructions. Use option '<a href="qh-optq.htm#Qu">Qu</a>'
for furthest-site Voronoi diagrams.
</blockquote>
<h3><a href="#TOP">»</a><a name="input">furthest-site qvoronoi
input</a></h3>
<blockquote>
<p>The input data on <tt>stdin</tt> consists of:</p>
<ul>
<li>dimension
<li>number of points</li>
<li>point coordinates</li>
</ul>
<p>Use I/O redirection (e.g., qvoronoi Qu < data.txt), a pipe (e.g., rbox 10 | qvoronoi Qu),
or the '<a href=qh-optt.htm#TI>TI</a>' option (e.g., qvoronoi TI data.txt Qu).
<p>For example, this is a square containing four random points.
Its furthest-site Voronoi diagram has on vertex and four unbounded,
separating hyperplanes (i.e., the coordinate axes)
<p>
<blockquote>
<tt>rbox c 4 D2 > data</tt>
<blockquote><pre>
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
</pre></blockquote>
<p><tt>qvoronoi Qu s Fo < data</tt>
<blockquote><pre>
Furthest-site Voronoi vertices by the convex hull of 8 points in 3-d:
Number of Voronoi regions: 8
Number of Voronoi vertices: 1
Number of non-simplicial Voronoi vertices: 1
Statistics for: RBOX c 4 D2 | QVORONOI Qu s Fo
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
4
5 4 5 0 1 0
5 4 6 1 0 0
5 5 7 1 0 0
5 6 7 0 1 0
</pre></blockquote>
</blockquote>
</blockquote>
<h3><a href="#TOP">»</a> <a name="outputs">furthest-site qvoronoi
outputs</a></h3>
<blockquote>
<p>These options control the output of furthest-site Voronoi diagrams.</p>
<blockquote>
<dl compact>
<dt> </dt>
<dd><b>furthest-site Voronoi vertices</b></dd>
<dt><a href="qh-opto.htm#p">p</a></dt>
<dd>print the coordinates of the furthest-site Voronoi vertices. The first line
is the dimension. The second line is the number of vertices. Each
remaining line is a furthest-site Voronoi vertex. The points-in-square example
has one furthest-site Voronoi vertex at the origin.</dd>
<dt><a href="qh-optf.htm#Fn">Fn</a></dt>
<dd>list the neighboring furthest-site Voronoi vertices for each furthest-site Voronoi
vertex. The first line is the number of Voronoi vertices. Each
remaining line starts with the number of neighboring vertices. Negative indices (e.g., <em>-1</em>) indicate vertices
outside of the Voronoi diagram. In the points-in-square example, the
Voronoi vertex at the origin has four neighbors-at-infinity.</dd>
<dt><a href="qh-optf.htm#FN">FN</a></dt>
<dd>list the furthest-site Voronoi vertices for each furthest-site Voronoi region. The first line is
the number of Voronoi regions. Each remaining line starts with the
number of Voronoi vertices. Negative indices (e.g., <em>-1</em>) indicate vertices
outside of the Voronoi diagram.
In the points-in-square example, all regions share the Voronoi vertex
at the origin.</dd>
<dt> </dt>
<dt> </dt>
<dd><b>furthest-site Voronoi regions</b></dd>
<dt><a href="qh-opto.htm#o">o</a></dt>
<dd>print the furthest-site Voronoi regions in OFF format. The first line is the
dimension. The second line is the number of vertices, the number
of input sites, and "1". The third line represents the vertex-at-infinity.
Its coordinates are "-10.101". The next lines are the coordinates
of the furthest-site Voronoi vertices. Each remaining line starts with the number
of Voronoi vertices in a Voronoi region. In 2-d, the vertices are
listed in adjacency order (unoriented). In 3-d and higher, the
vertices are listed in numeric order. In the points-in-square
example, each unbounded region includes the Voronoi vertex at
the origin. Lines consisting of <em>0</em> indicate
interior input sites. </dd>
<dt><a href="qh-optf.htm#Fi2">Fi</a></dt>
<dd>print separating hyperplanes for inner, bounded furthest-site Voronoi
regions. The first number is the number of separating
hyperplanes. Each remaining line starts with <i>3+dim</i>. The
next two numbers are adjacent input sites. The next <i>dim</i>
numbers are the coefficients of the separating hyperplane. The
last number is its offset. The are no bounded, separating hyperplanes
for the points-in-square example.</dd>
<dt><a href="qh-optf.htm#Fo2">Fo</a></dt>
<dd>print separating hyperplanes for outer, unbounded furthest-site Voronoi
regions. The first number is the number of separating
hyperplanes. Each remaining line starts with <i>3+dim</i>. The
next two numbers are adjacent input sites on the convex hull. The
next <i>dim</i>
numbers are the coefficients of the separating hyperplane. The
last number is its offset. The points-in-square example has four
unbounded, separating hyperplanes.</dd>
<dt> </dt>
<dt> </dt>
<dd><b>Input sites</b></dd>
<dt><a href="qh-optf.htm#Fv2">Fv</a></dt>
<dd>list ridges of furthest-site Voronoi vertices for pairs of input sites. The
first line is the number of ridges. Each remaining line starts with
two plus the number of Voronoi vertices in the ridge. The next
two numbers are two adjacent input sites. The remaining numbers list
the Voronoi vertices. As with option 'o', a <em>0</em> indicates
the vertex-at-infinity
and an unbounded, separating hyperplane.
The perpendicular bisector (separating hyperplane)
of the input sites is a flat through these vertices.
In the points-in-square example, the ridge for each edge of the square
is unbounded.</dd>
<dt> </dt>
<dt> </dt>
<dd><b>General</b></dd>
<dt><a href="qh-opto.htm#s">s</a></dt>
<dd>print summary of the furthest-site Voronoi diagram. Use '<a
href="qh-optf.htm#Fs">Fs</a>' for numeric data.</dd>
<dt><a href="qh-opto.htm#i">i</a></dt>
<dd>list input sites for each <a href=qdelau_f.htm>furthest-site Delaunay region</a>. Use option '<a href="qh-optp.htm#Pp">Pp</a>'
to avoid the warning. The first line is the number of regions. The
remaining lines list the input sites for each region. The regions are
oriented. In the points-in-square example, the square region has four
input sites. In 3-d and higher, report cospherical sites by adding extra points.
</dd>
<dt><a href="qh-optg.htm#G">G</a></dt>
<dd>Geomview output for 2-d furthest-site Voronoi diagrams.</dd>
</dl>
</blockquote>
</blockquote>
<h3><a href="#TOP">»</a> <a name="controls">furthest-site qvoronoi
controls</a></h3>
<blockquote>
<p>These options provide additional control:</p>
<blockquote>
<dl compact>
<dt><a href="qh-optq.htm#Qu">Qu</a></dt>
<dd>must be used.</dd>
<dt><a href="qh-optq.htm#QVn">QVn</a></dt>
<dd>select furthest-site Voronoi vertices for input site <em>n</em> </dd>
<dt><a href="qh-optt.htm#Tv">Tv</a></dt>
<dd>verify result</dd>
<dt><a href="qh-optt.htm#TO">TI file</a></dt>
<dd>input data from file. The filename may not use spaces or quotes.</dd>
<dt><a href="qh-optt.htm#TO">TO file</a></dt>
<dd>output results to file. Use single quotes if the filename
contains spaces (e.g., <tt>TO 'file with spaces.txt'</tt></dd>
<dt><a href="qh-optt.htm#TFn">TFn</a></dt>
<dd>report progress after constructing <em>n</em> facets</dd>
<dt><a href="qh-optp.htm#PDk">PDk:1</a></dt>
<dd>include upper and lower facets in the output. Set <em>k</em>
to the last dimension (e.g., 'PD2:1' for 2-d inputs). </dd>
<dt><a href="qh-opto.htm#f">f </a></dt>
<dd>facet dump. Print the data structure for each facet (i.e.,
furthest-site Voronoi vertex).</dd>
</dl>
</blockquote>
</blockquote>
<h3><a href="#TOP">»</a> <a name="graphics">furthest-site qvoronoi
graphics</a></h3>
<blockquote>
<p>In 2-d, Geomview output ('<a href="qh-optg.htm#G">G</a>')
displays a furthest-site Voronoi diagram with extra edges to
close the unbounded furthest-site Voronoi regions. All regions
will be unbounded. Since the points-in-box example has only
one furthest-site Voronoi vertex, the Geomview output is one
point.</p>
<p>See the <a href="qh-eg.htm#delaunay">Delaunay and Voronoi
examples</a> 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. </p>
</blockquote>
<h3><a href="#TOP">»</a><a name="notes">furthest-site qvoronoi
notes</a></h3>
<blockquote>
<p>See <a href="qvoronoi.htm#notes">Voronoi notes</a>.</p>
</blockquote>
<h3><a href="#TOP">»</a><a name="conventions">furthest-site qvoronoi conventions</a></h3>
<blockquote>
<p>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 <a
href="qconvex.htm#conventions">qconvex conventions</a>, <a
href="qdelau_f.htm#conventions">furthest-site delaunay
conventions</a>, and <a href="index.htm#structure">Qhull's data structures</a>.</p>
<ul>
<li><em>input site</em> - a point in the input (one dimension
lower than a point on the convex hull)</li>
<li><em>point</em> - a point has <i>d+1</i> coordinates. The
last coordinate is the sum of the squares of the input
site's coordinates</li>
<li><em>vertex</em> - a point on the upper facets of the
paraboloid. It corresponds to a unique input site. </li>
<li><em>furthest-site Delaunay facet</em> - an upper facet of the
paraboloid. The last coefficient of its normal is
clearly positive.</li>
<li><em>furthest-site Voronoi vertex</em> - the circumcenter
of a furthest-site Delaunay facet</li>
<li><em>furthest-site Voronoi region</em> - 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.</li>
<li><em>furthest-site Voronoi diagram</em> - the graph of the
furthest-site Voronoi regions with the ridges (edges)
between the regions.</li>
<li><em>infinity vertex</em> - the Voronoi vertex for
unbounded furthest-site Voronoi regions in '<a
href="qh-opto.htm#o">o</a>' output format. Its
coordinates are <em>-10.101</em>.</li>
<li><em>good facet</em> - an furthest-site Voronoi vertex with
optional restrictions by '<a href="qh-optq.htm#QVn">QVn</a>',
etc.</li>
</ul>
</blockquote>
<h3><a href="#TOP">»</a><a name="options">furthest-site qvoronoi options</a></h3>
<blockquote>
See <a href="qvoronoi.htm#options">qvoronoi options</a>. The same
program is used for both constructions. Use option '<a href="qh-optq.htm#Qu">Qu</a>'
for furthest-site Voronoi diagrams.
</blockquote>
<!-- Navigation links -->
<hr>
<p><b>Up:</b> <a href="http://www.qhull.org">Home page</a> for Qhull<br>
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
• <a href="qh-quick.htm#options">Options</a>
• <a href="qh-opto.htm#output">Output</a>
• <a href="qh-optf.htm#format">Formats</a>
• <a href="qh-optg.htm#geomview">Geomview</a>
• <a href="qh-optp.htm#print">Print</a>
• <a href="qh-optq.htm#qhull">Qhull</a>
• <a href="qh-optc.htm#prec">Precision</a>
• <a href="qh-optt.htm#trace">Trace</a>
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
<b>To:</b> <a href="#synopsis">sy</a>nopsis
• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs
• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics
• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions
• <a href="#options">op</a>tions
<!-- GC common information -->
<hr>
<p><a href="http://www.geom.uiuc.edu/"><img src="qh--geom.gif"
align="middle" width="40" height="40"></a><i>The Geometry Center
Home Page </i></p>
<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
</a><br>
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
</body>
</html>
|
