1,721,191 research outputs found
Fitting a graph to one-dimensional data
No full textGiven n data points in Rd, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regression problems. The graph proposed by Daitch, Kelner and Spielman (ICML 2009) can be computed by quadratic programming and hence in polynomial time. While a more efficient algorithm would be preferable, replacing quadratic programming is challenging even for the special case of points in one dimension. We develop a dynamic programming algorithm for this case that runs in O(n2) time under the Real-RAM model, where arithmetic on real numbers takes constant time.</p
Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons
No full text
Exact and approximate algorithms for Fréchet problems
No full textThe advances of location-acquisition and mobile devices generate massive trajectory data and motivate trajectory ananlysis. Fréchet distance is a popular metric for measuring the similarity between trajectories. It appears in many algorithmic problems in trajectory analysis including curve simplification, clustering, nearest neighbor, and range searching queries. We present new algorithms for these problems under the Fréchet distance. For curve simplification, we present a novel space of configurations and a useful geometric construct that lead us to the first bicriteria approximation scheme for curve simplification. We further extend these notions to a set of curves, and design an algorithm to compute a simplified representative for multiple curves. By combining this technique with a framework in the literature, we obtain the first approximation algorithm for (k, l)-median clustering under Fréchet distance. We then study the nearest neighbor problem. We design a scheme that allows us to transform a query curve into an encoding from a finite space. This encoding enables us to design the first approximate nearest neighbor data structure for polygonal curves in Rdunder Fréchet distance that has a space complexity dependent on the input size only. We characterize Fréchet distance by a polynomial system and develop an algebraic geometric approach. This new algebraic perspective allows us to design exact algorithms for a wide range of problems including curve simplification, nearest neighbor and range searching, which are hitherto unknown. Finally, we study the computational complexity and approximability of the Fréchet distance. We design the first subquadratic time algorithm for computing the Fréchet distance. We also show the first constant approximation algorithm for the Fréchet distance that runs in strongly subquadratic time.</p
On the sizes of Delaunay meshes
No full textAbstractLet P be a polyhedral domain occupying a convex volume. We prove that the size of a graded mesh of P with bounded vertex degree is within a factor O(HP3) of the size of any Delaunay mesh of P with bounded radius-edge ratio. The term HP depends on the geometry of P and it is likely a small constant when the boundaries of P are fine triangular meshes. There are several consequences. First, among all Delaunay meshes with bounded radius-edge ratio, those returned by Delaunay refinement algorithms have asymptotically optimal sizes. This is another advantage of meshing with Delaunay refinement algorithms. Second, if no input angle is acute, the minimum Delaunay mesh with bounded radius-edge ratio is not much smaller than any minimum mesh with aspect ratio bounded by a particular constant
Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
Full text linkThe 2-opt heuristic is a very simple local search heuristic for the traveling salesman problem. While it usually converges quickly in practice, its running-time can be exponential in the worst case. In order to explain the performance of 2-opt, Englert, Röglin, and Vöcking (Algorithmica, to appear) provided a smoothed analysis in the so-called one-step model on d-dimensional Euclidean instances. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation , yields a bound that is only polynomial in and . We prove bounds that are polynomial in and for the smoothed running-time with Gaussian perturbations. In particular our analysis for Euclidean distances is much simpler than the existing smoothed analysis
Note on a class of admission control policies for the stochastic knapsack problem
Full text linkIn this note we discuss a class of exponential penalty function policies recently proposed by Iyengar and Sigman for controlling a stochastic knapsack. These policies are based on the optimal solution of some related deterministic linear programs. By finding explicitly their optimal solution, we reinterpret the exponential penalty function policies and show that they belong to the class of threshold policies. This explains their good practical behavior, facilitates the comparison with the thinning policy, simplifies considerably their analysis and improves the bounds previously proposed
- …
