Using Gale transforms in computational geometry

LetP denote a set ofn d+1 points ind-space ^d . A Gale transform ofP assigns to each point inP a vector in space ^n-d-1 such that the resultingn-tuple of vectors reflects all affinely invariant properties ofP. 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.