Pankaj Agarwal was supported in part by National Science Foundation research grant CCR-93-01259, by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by a National Science Foundation NYI award and matching funds from Xerox Corp, and by a grant from the U.S.-Israeli Bi-national Science Foundation. Julien Basch, Leonidas Guibas, and Li Zhang were supported in part by National Science Foundation grant CCR-9623851 and by US Army MURI grant DAAH04-96-1-0007. We wish to acknowledge the contribution of Otfried Cheong and Mark de Berg to preliminary work related to part of this paper.