Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
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.
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI