DT and CH on the Sphere (redux)

A light bulb just went off in my head, and I thought I'd share (and ask a couple of questions).

Recall that I want to compute Delaunay Triangulations of a "convex" (whatever that means) patch of points on a portion of the sphere - specifically, excluding a region near one pole. The patch covers MORE than a hemisphere, in general.

Computing the DT of the points on the unrestricted sphere is no problem - as everyone pointed out, the boundary of the 3D convex hull of a set of points on the sphere is equivalent to the DT of those points computed on the sphere.

The sticking point was in defining the boundary separating the patch from the forbidden polar region. We discussed two methods:

a) include the pole, and then discard (or treat specially) faces
that involve the pole, and

b) do NOT include the pole, but discard faces that can SEE the pole.

All of this will work just fine, but (lazy man that I am) I was reluctant to abandon ancient (time tested, debugged, proven robust) 2D DT (and CH) code for points in the plane. Among other things, this 20yo code was a testament to the obscene lengths we once went to to optimize out hotspots, and contained some "cute" geometric hacks.

Also, for visualization purposes we routinely present this data in the Riemann Projection. This projection "emphasizes" the region near the INcluded pole while de-emphasizing (and distorting) the region near the forbidden pole. As an expediency hack, we occasionally use the Riemann Projection to get the points onto the plane, and do CH and DT computations using this (distorted) point set. This has been more than adequate (see the May 8, 1987 cover of _Science_), so it has gone unexamined for a long time. (it actually makes sense when the point of the triangulation is to smoothly shade a function defined by measurements at the points - displayed using the RP).

There is a well known projection (originally due to K. Brown in 1979, I think) from the plane to the paraboloid - which established a connection between 3D CH boundaries and the planar DT. I was looking for something like this - but mapping the plane to/from the SPHERE and not the paraboloid.

And then...the dim bulb finally lit up...and I remembered that Stereographic Projection is conformal. This means (I think) that mapping points from the sphere (minus one pole) to the plane using SP and then computing the 2D CH and 2D DT (and then lifting the mesh back onto the sphere) will work very nicely.

Which means I get to keep my old, clunky 2D code (or, I can always map from the plane up to the paraboloid...).

So - two questions for the comp geometry gurus:

a) does this analysis hold water?

b) given a 2D CH in the SP of the sphere - how should we interpret the boundary of the CH when mapped back to the sphere? Is there any sense in which this is the boundary of a "convex" region of the sphere (minus the pole)?


--
Kenneth Sloan KennethRSloan@xxxxxxxxx
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
.

Relevant Pages

  • Re: Principal components analysis of 3D directional data
    ... PCA directly to the x,y,z components of the unit vectors however this is not ... If you imagine two points on a sphere, PCA of their x,y,z ... The idea I've been playing with is using a map projection technique to ... vectors) onto a 2D plane. ...
    (sci.stat.math)
  • Re: Is infinite Euclidean space non-euclidean?
    ... circle will also then, as you say, have an infinite length. ... of projecting the sphere, ... You can assume that the projection is to a plane which is tangential ...
    (sci.logic)
  • Re: unwrapping a sphere
    ... > A very simple algorithm for a sphere is to simply ... of a sphere onto a plane, then any scheme will introduce distortion ... What you propose is called an "equidistant cylindrical projection", ... the surface of the sphere along rays emanating from the south pole. ...
    (comp.graphics.algorithms)
  • Re: unwrapping a sphere
    ... Now your sphere mesh will be unwrapped on the XY plane, ... which is a variation of a Mercator projection. ... the surface of the sphere along rays emanating from the south pole. ...
    (comp.graphics.algorithms)
  • Re: a tangency thought experiment
    ... four times your height, which is at rest on the plane, ... Thus the sphere shares exactly one point ... tangency. ... ceiling, in your vicinity, becomes increasingly flat ...
    (sci.math)