Splitting a configuration in a simplex (Q2366245)

The 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 \(i\)-th facet of \(T\). Let \(S\) be a set of \(n\) points in \(T\), and let \(\pi\) be a sequence of nonnegative integers \(\pi_ 1,\ldots,\pi_{d+1}\) satisfying \(\sum^{d+1}_{i=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,\ldots,d+1\). The associated dissection in 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(d^ 2n\log n+d^ 3n)\) 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.