From: s.havemann at tu-bs.de (Sven Havemann)
Date: Mon, 26 Apr 1999 19:36:40 +0200
Subject: SOLUTION: Triangulation of the unit sphere
Message-ID: <3724A428.138357DC@tu-bs.de>
Content-Length: 1977
X-UID: 890                                                  

Hi!
===

I have a neat C++ solution for the problem of finding a triangulation of
n random points distributed on the unit sphere. The algorithm runs in
O(n*sqrt(n)) with a nice small constant, as you can see below (SGI O2
with 250 MHz MIPS R10000). 

Python (www.python.org) and PyOpenGL
(http://starship.python.net/crew/da/PyOpenGL/) have been _very_ helpful,
and there's a nice unit sphere viewer and algorithm visualization
included in the 8K .tgz for those unixers who have it installed (I can
build a windows VC++ version on demand).

Have a look:
ftp://ftp.cg.cs.tu-bs.de/pub/cg/people/havemann/sdelaunay-1.00.tgz

Greetings, Sven.

===============================================================

1004 faces, 504 vertices, 0.065275 seconds
2004 faces, 1004 vertices, 0.138277 seconds
3004 faces, 1504 vertices, 0.213124 seconds
4004 faces, 2004 vertices, 0.323524 seconds
5004 faces, 2504 vertices, 0.416665 seconds
6004 faces, 3004 vertices, 0.520598 seconds
7004 faces, 3504 vertices, 0.655553 seconds
8004 faces, 4004 vertices, 0.757154 seconds
9004 faces, 4504 vertices, 0.887238 seconds
10004 faces, 5004 vertices, 1.024282 seconds
11004 faces, 5504 vertices, 1.160054 seconds
12004 faces, 6004 vertices, 1.327187 seconds
13004 faces, 6504 vertices, 1.466274 seconds
14004 faces, 7004 vertices, 1.627190 seconds
15004 faces, 7504 vertices, 1.818125 seconds
16004 faces, 8004 vertices, 1.988085 seconds
17004 faces, 8504 vertices, 2.169752 seconds
18004 faces, 9004 vertices, 2.370354 seconds
19004 faces, 9504 vertices, 2.549433 seconds
20004 faces, 10004 vertices, 2.751907 seconds

-- 
__________________________________________________________________
 dipl-inform. Sven Havemann        Institut fuer ComputerGraphik
 Odastrasse 6                      Rebenring 18
 38122 Braunschweig - Germany      38106 Braunschweig - Germany
 Tel. 0531/2808955                 Tel. 0531/391-2108, Fax: -2103
 mailto:s.havemann at tu-bs.de        http://www.cg.cs.tu-bs.de




