1,721,026 research outputs found
Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals: Proc. 12th International Computer Science Symposium in Russia
No full textWe present a data structure to maintain a set of intervals on the real line subject to fast insertions and deletions of the intervals, stabbing queries, and local updates. Intuitively, a local update replaces an interval by another one of roughly the same size and location. We investigate whether local updates can be implemented faster than a deletion followed by an insertion. We present the first results for this problem for sets of possibly overlapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, deletions and stabbing queries in time O(logn)O(logn) , and local updates in time O(logn/loglogn)O(logn/loglogn) , where n is the number of intervals. We also analyze the dependence on the ply when it is not constant. Our results are adaptive: the times depend on the current ply at the time of each operation
Unions of Onions: Preprocessing Imprecise Points for Fast Onion Layer Decomposition
No full textLet D be a set of n pairwise disjoint unit disks in the plane. We describe how to build a data structure for D so that for any point set P containing exactly one point from each disk, we can quickly nd the onion decomposition (convex layers) of P. Our data structure can be built in O(n log n) time and has linear size. Given P, we can nd its onion decomposition in O(n log k) time, where k is the number of layers. We also provide a matching lower bound. Our solution is based on a recursive space decomposition, combined with a fast algorithm to compute the union of two disjoint onion decompositions
Realistic Analysis for Algorithmic Problems on Geographical Data
No full textThe worst-case analysis is a key element of the performance analysis of algorithms. When it comes to spatial data, such as paths of moving objects and digital terrain models, the theoretical worst case may be a contrived configuration which would never occur in practice. In this case the algorithmic analysis may fail to describe the actual behavior of an algorithm. To remedy this, a collection of techniques have been developed, which enable a realistic analysis with mathematically provable bounds. Realistic input models capture geometric parameters such as the distribution and shape of the input objects. This allows for a specific analysis that takes the difficulty of the input instance into account and is therefore also meaningful for input instances that are less difficult. In this thesis we revisit some well-studied problems of computational geometry with a realistic analysis. We first study the Frechet distance, a similarity measure for outlines of shapes or paths of moving objects. Under a new realistic input model, we can approximate the Frechet distance in near-linear time, where previous algorithms run in quadratic time. We extend our algorithm so that it can be applied to a sophisticated variant, the shortcut Frechet distance, which captures partial similarity. We show that computing this new variant exactly is NP-hard. Along the way, we develop data structures to answer Frechet-distance queries. In the second part of the thesis, we study computations on digital terrain models, which represent geographic regions. A terrain model can be used to simulate where rain water flows to, which is useful for flood prediction for instance. Although these computations are extremely sensitive to elevation error, none of the known algorithms take noise into account. We develop a theory that enables robust and efficient hydrological computations if the elevation data from which the terrain model was derived was imprecise. While the new theory uses fixed flow directions, we also show that an extension of our methods to continuous directions will be difficult. In particular, we show that it is NP-hard to determine if there can be a steepest descent path between two points on an imprecise polyhedral surface. The Voronoi diagram is an important geometric structure that can be used to answer queries for the closest point of interest. The "closeness" can be defined by the length of the shortest path along the terrain surface. The efficiency depends among other things on the amount of space taken up by the diagram. According to the classical worst-case analysis the space grows quadratically with the size of the terrain. However, this quadratic behavior cannot be observed in practice. In the last part of the thesis we analyze the size of the Voronoi diagram under the assumption that the points of interest are distributed uniformly on the terrain surface. Our results confirm a conjecture by Aronov, de Berg and Thite from 2008 that in a realistic setting the complexity of the diagram is additively linear in the size of the terrain and the number of sites
Clear Unit-Distance Graphs
No full textWe introduce a variation of unit-distance graphs which we call emph clear unit-distance graphs. They require the pairwise distances of the representing points to be either exactly 1 or not close to 1. We discuss properties and applications of clear unit-distance graphs
Central Trajectories
No full textAn important task in trajectory analysis is clustering. The results of a clustering are often summarized by a single representative trajectory and an associated size of each cluster. We study the problem of computing a suitable representative of a set of similar trajectories. To this end we define a central trajectory CC, which consists of pieces of the input trajectories, switches from one entity to another only if they are within a small distance of each other, and such that at any time tt, the point C(t)C(t) is as central as possible. We measure centrality in terms of the radius of the smallest disk centered at C(t)C(t) enclosing all entities at time tt, and discuss how the techniques can be adapted to other measures of centrality. We first study the problem in R1R1, where we show that an optimal central trajectory CC representing nn trajectories, each consisting of ττ edges, has complexity Θ(τn2)Θ(τn2) and can be computed in O(τn2logn)O(τn2logn) time. We then consider trajectories in RdRd with d≥2d≥2, and show that the complexity of CC is at most O(τn5/2)O(τn5/2) and can be computed in O(τn3)O(τn3) time
A Comparative Study of k-Nearest Neighbour Techniques in Crowd Simulation
Full text linkThe k-nearest neighbour (kNN) problem appears in many different fields of computer science, such as computer animation and robotics. In crowd simulation, kNN queries are typically used by a collision-avoidance method to prevent unnecessary computations. Many different methods for finding these neighbours exist, but it is unclear which will work best in crowd simulations, an application which is characterised by low dimensionality and frequent change of the data points. We therefore compare several data structures for performing kNN queries. We find that the nanoflann implementation of a k-d tree offers the best performance by far on many different scenarios, processing 100,000 agents in about 35 milliseconds on a fast consumer PC
Critical Placements of a Square or Circle amidst Trajectories for Junction Detection
No full textMotivated by automated junction recognition in tracking data, we study a problem of placing a square or disc of fixed size in an arrangement of lines or line segments in the plane. We let distances among the intersection points of the lines and line segments with the square or circle define a clustering, and study the complexity of \emph{critical} placements for this clustering. Here critical means that arbitrarily small movements of the placement change the clustering. A parameter ε defines the granularity of the clustering. Without any assumptions on ε, the critical placements have a trivial O(n4) upper bound. When the square or circle has unit size and 0<ε<1 is given, we show a refined O(n2/ε2) bound, which is tight in the worst case. We use our combinatorial bounds to design efficient algorithms to compute junctions. As a proof of concept for our algorithms we have a prototype implementation that showcases their application in a basic visualization of a set of n trajectories and their k most important junctions
Practical Approaches to Partially Guarding a Polyhedral Terrain
No full textWe study the problem of placing guard towers on a terrain such that the terrain can be seen from at least one tower. This problem is important in many applications, and has an extensive history in the literature (known as, e.g., multiple observer siting). In this paper, we consider the problem on polyhedral terrains, and we allow the guards to see only a fixed fraction of the terrain, rather than everything. We experimentally evaluate how the number of required guards relates to the fraction of the terrain that can be covered. In addition, we introduce the concept of dominated guards, which can be used to preprocess the potential guard locations and speed up the subsequent computations. » » Look Inside MyCopy Softcover Edition 24.99 EUR/USD/GBP/CHF Buy Now Other actions Reprints and Permissions Export citatio
- …
