Browse Prior Art Database

# Voronoi Diagram Construction Using Sobol Sequences

IP.com Disclosure Number: IPCOM000107425D
Original Publication Date: 1992-Feb-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 42K

IBM

## Related People

Tezuka, S: AUTHOR [+1]

## Abstract

An algorithm is disclosed that efficiently computes a Voronoi diagram for a given point set. The procedure of the algorithm is as follows: Assume that N points are in the unit square S=((x,y)| 0

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Voronoi Diagram Construction Using Sobol Sequences

An algorithm is disclosed that efficiently computes a
Voronoi diagram for a given point set. The procedure of the algorithm
is as follows:  Assume that N points are in the unit square S=((x,y)|
0<x<1,0<y<1). Let k be an integer with 2**(2k-1)< N < 2**(2k). Divide
S into M= **(2k) buckets as B(i,j) = ((x,y)|i2**(-k)<x<(i+1)2**(-k),
j2**(-k)<y<(j+1)2**(-k)), for 0 < i,j <2**(k). Let a Sobol sequence
be Pn = (Xn,Yn), n=1,2,..., where 0 < Xn, Yn < 1.
ALGORITHM

The approach is based on an incremental method. For n=0, no
point is in the square. For n=1,2,...,M,
Step 1: Based on a Sobol sequence Pn, pick up all points in a bucket
B(L2**(k)Xn , L2**(k)Yn ).
Step 2:  Add the points as new points into the Voronoi diagram thus
far obtained for the previous points, and adjust the diagram.
Step 3: If n is not M, go to Step 1; otherwise, end.
EXAMPLE

The first 16 points of a Sobol sequence: S0=(0,0),
S1=(0.1,0.1), S2=(0.01,0.11), S3=(0.11,0.01), S4=(0.001,0.101),
S5=(0.101,0.001), S6=(0.011,0.011), S7=(0.111,0.111),
S8=(0.0001,0.1111), S9=(0.1001,0.0111), S10=(0.0101,0.0011),
S11=(0.1101,0.1011), S12=(0.0011,0.0101), S13=(0.1011,0.1101),
S14=(0.0111,0.1001), S15=(0.1111,0.0001), ....

Based on this sequence, the 16 buckets in the figure are
selected uniformly. The number in each bucket means the order of
selection. Note that the first four buckets are also uniformly
chosen.