Using Gale transforms in computational geometry

F. Aurenhammer


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 sketches applications to convex hull and visibility problems. An application to scene analysis is worked out in some more detail.

Reference: F. Aurenhammer. Using Gale transforms in computational geometry. In Proc. $4^{th}$ Workshop on Computational Geometry CG '88, Lecture Notes in Computer Science, volume 333, pages 202-216, Wuerzburg, Germany, 1988. Springer Verlag.