Narrow Results

We give a practical and provably good Monte Carlo algorithm for approximating center points. Let P be a set of n points in R^d. A point c∈R^d is a β-center point of P if every closed halfspace containing c contains at least βn points of P. Every point set has a 1/(d+1)-center point; our algorithm finds an Ω(1/d²)-center point with high probability. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O(log²d log log n) time. Our algorithm has been used in mesh partitioning methods and can be used in the construction of high breakdown estimators for multivariate datasets in statistics. It has the potential to improve results in practice for constructing weak ∊-nets. We derive a variant of our algorithm whose time bound is fully polynomial in d and linear in n, and show how to combine our approach with previous techniques to compute high quality center points more quickly.

This paper constructs a deformation model for the ancient tower using four groups of observational data and by plotting and calculating the center of each layer to find scenarios where the tower would experience deformation such as bending and tilting. Furthermore, the inclination angle with respect to OZ axis of each layer and the tilt circumstances of the entire tower are discussed. To obtain the degree of distortion of each layer, this paper uses the continuous curve’s curvature definition and averaged the curvature. The average distortion in each layer from two time periods: July 1986 to August 1996, and from March 2009 to March 2011, is calculated using the formula of plane’s distortion degree.