Topics in Computational Geometry
John Zolnowsky · 2018
of S, distinct from p which minimizes the distance from p. Bounds for the time for finding the nearest neighbor of all points are bound by use of the k-d data structure. Three different criteria for choosing the partition ordinate of each node in the k-d tree, based on the test point set are examined. Tight bounds for the best of these criteria, which generates the ''square tree'', are obtained. The second problem is to construct efficiently the intersection of a finite set of half-spaces in three dimensions. If N is the number of half-spaces, the algorithm takes time proportional to N logN. Intuitively, the algorithm first constructs a northern and a southern cap, then intersects these two polyhedra to generate the result polyhedron. After cap construction, space is vertically stratified into slabs by horizontal planes passed through the vertices of the caps. By use of a binary search, an edge of the final intersection can be found, and this edge is extended around the polyhedron to complete the intersection. 11 figures, 2 tables.