Using Gale transforms in computational geometry

F. Aurenhammer

Abstract:

Let $P$ denote a set of $n \geq d+1$ points in $d$-space $R^d$. A Gale transform of $P$ assigns to each point in $P$ a vector in space $R^{d+1}$ such that the resulting $n$-tuple of vectors reflects all affinely invariant properties of $P$. First utilized by Gale in the 1950s, Gale transforms have been recognized as a powerful tool in combinatorial geometry. This paper introduces Gale transforms to computational geometry. It offers a direct algorithm for their construction and addresses applications to convex hull and visibility problems. An application to scene analysis is worked out in detail.

Reference: F. Aurenhammer. Using Gale transforms in computational geometry. Mathematical Programming, B 52:179-190, 1991. Special Issue. [IIG-Report-Series 248, TU Graz, Austria, 1988].