About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
This paper presents a new method of partition, named π-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 π be a sequence of nonnegative integers π1, ..., nd+1 satisfying σi=1d+1π1=n The π-splitter of (T, S) is a point G in T such that T(G;i) contains at least πi points of S in its closure for every i=1, 2, ..., d + 1. The associated dissection is the re-splitting. The existence of a π-splitting is shown for any (T, S) and π, 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 re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given. © 1993 Springer-Verlag New York Inc.