Sublinear time width-bounded separators and their application to the protein side-chain packing problem

Given d>2 and a set of n grid points Q in ℜ ^d , we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in sublinear time such that Q has at most points on either side of the hyper-plane, and at most points within distance to the hyper-plane, where c _d is a constant for fixed d. In particular, c ₃=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005). This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35. The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA.