This paper introduces a new proximity graph, called the @math -Semi-Yao graph ( @math -SYG), on a set @math of points in @math , which is a supergraph of the @math -nearest neighbor graph ( @math -NNG) of @math . We provide a kinetic data structure (KDS) to maintain the @math -SYG on moving points, where the trajectory of each point is a polynomial function whose degree is bounded by some constant. Our technique gives the first KDS for the theta graph ( , @math -SYG) in @math . It generalizes and improves on previous work on maintaining the theta graph in @math . As an application, we use the kinetic @math -SYG to provide the first KDS for maintenance of all the @math -nearest neighbors in @math , for any @math . Previous works considered the @math case only. Our KDS for all the @math -nearest neighbors is deterministic. The best previous KDS for all the @math -nearest neighbors in @math is randomized. Our structure and analysis are simpler and improve on this work for the @math case. We also provide a KDS for all the @math -nearest neighbors, which in fact gives better performance than previous KDS's for maintenance of all the exact @math -nearest neighbors. As another application, we present the first KDS for answering reverse @math -nearest neighbor queries on moving points in @math , for any @math .
For a set of @math moving points in @math , where each trajectory of a point is a polynomial function of degree bounded by constant @math , Basch, Guibas, and Hershberger @cite_3 provided a KDS for maintenance of the closest pair. Their KDS uses linear space and processes @math events, each in time @math . Here, @math is an extremely slow-growing function.
@cite_3
2175772512 2110785107 1947202642 2787445655
This paper presents a kinetic data structure (KDS) for maintenance of the Euclidean minimum spanning tree (EMST) on a set of moving points in 2-dimensional space. For a set of n points moving in the plane we build a KDS of size O(n) in O(nlogn) preprocessing time by which the EMST is maintained efficiently during the motion. This is done by applying the required changes to the combinatorial structure of the EMST which is changed in discrete timestamps. We assume that the motion of the points, i.e. x and y coordinates of the points, are defined by algebraic functions of constant maximum degree. In terms of the KDS performance parameters, our KDS is responsive, local, and compact. The presented KDS is based on monitoring changes of the Delaunay triangulation of the points and edge-length changes of the edges of the current Delaunay triangulation. We consider the functions @math defined as the @math th partial derivative of Lebesgue's singular function @math with respect to @math at @math . This sequence includes a multiple of the Takagi function as the case @math . We show that @math is continuous but nowhere differentiable for each @math , and determine the Holder order of @math . From this, we derive that the Hausdorff dimension of the graph of @math is one. Using a formula of Lomnicki and Ulam, we obtain an arithmetic expression for @math using the binary expansion of @math , and use this to find the sets of points where @math and @math take on their absolute maximum and minimum values. We show that these sets are topological Cantor sets. In addition, we characterize the sets of local maximum and minimum points of @math and @math . We propose a new randomized coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel, and PROXimal; this is the first time such a method is proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate @math , where @math is the iteration counter, @math is a data-weighted average degree of separability of the loss function, @math is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and @math is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of accelerated coordinate descent. The fact that the method depends on the average degree of separability, and not on the maximum degree... This paper analyzes the iteration-complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. More specifically, the objective function is of the form @math where @math is a differentiable function whose gradient is Lipschitz continuous and @math is a closed convex function with bounded domain. The method, basically, consists of applying an accelerated inexact proximal point method for solving approximately a sequence of quadratic penalized subproblems associated to the linearly constrained problem. Each subproblem of the proximal point method is in turn approximately solved by an accelerated composite gradient method. It is shown that the proposed scheme generates a @math -approximate stationary point in at most @math . Finally, numerical results showing the efficiency of the proposed method are also given.