SPLITTING A CONFIGURATION IN A SIMPLEX

This paper presents a new method of partition, named pi-splitting, of a point set in d-dimensional space. Given a point G in a d-dimensional simplex T, T(G; i) is the subsimplex spanned by G and the ith facet of T Let S be a set of n points in T, and let pi be a sequence of nonnegative integers pi1, ..., pi(d+1) satisfying SIGMA(i=1)d+1 pi(i) = n. The pi-splitter of (T, S) is a point G in T such that T(G; i) contains at least pi(i) points of S in its closure for every i = 1, 2, ..., d + 1. The associated dissection is the pi-splitting. The existence of a pi-splitting is shown for any (T, S) and pi, and two efficient algorithms for finding such a splitting are given. One runs in O(d2n log n + d3n) time, and the other runs in O(n) time if the dimension d can be considered as a constant. Applications of pi-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.