(20) Voronoi Diagram Construction Program

	Machine:     Multi-PSI
	Environment: PIMOS
	Language:    GDCC
	Source Code: 260 KB
	Documents:   Manual (Japanese)

Overview

This program constructs a Voronoi Diagram which is an essential concept of Computational geometry.

Characteristics

Voronoi Diagram is an essential concept of Computational geometry, and this is widely used in various application areas.

The algorithm of this program is O(N)(N is the number of given points) in calculation time, that is the same order as the most effective algorithm which is well known.

And this algorithm is high degree of parallelism, so parallel speedup is obtained using any processors.

Function

Voronoi Diagram of a finite set S of points in the plane is a partition so that each region is a set of points which is closer to a point in S in the region than to any other points in S.

This program constructs a Voronoi Diagram of a finite set S of given points in the plane.

It is written in GDCC, parallel constraint logic programming language, and you can execute this program on Multi-PSI.

FTP

www-admin@icot.or.jp