We consider the problem of quickly providing strong lower bounds for the planar Euclidean shortest path (ESP) problem. Such lower bounds are crucial for guiding the search in A* type approaches or for proving quality guarantees for algorithms that compute approximate solutions. Our contributions are two-fold: we show how to simplify ESP instances such that computing and storing a visibility graph becomes feasible while distances within the simplified instance are guaranteed to constitute lower bounds for the original problem instance. Furthermore we show how to precompute a space efficient data structure that allows to perform distance queries on visibility graphs within few microseconds with negligible space overhead.

We consider the problem of reducing the search space of algorithms which solve the Euclidean Shortest Path Problem by traversing a precomputed navigation mesh. Heuristics can be used to guide this traversal. We show how upper and lower bounds to the optimal path length can be combined into an independent heuristic which considerably reduces the search space of such an algorithm. In our experiments we use our heuristic in an existing routing algorithm and find that our approach yields a substantial speedup for complicated paths.

The radius of a graph is an important structural parameter which plays a key role in social network analysis and related applications. It measures the minimum shortest path distance that is required to reach all nodes in the graph from a single node. A node from which all other nodes are within a distance equal to the radius is called a center of the graph. In a graph with n nodes and m edges, the center and the radius can be determined in Õ(nm) by computing shortest path distances between all pairs of nodes. Fine-grained complexity results suggest that asymptotically faster algorithms are unlikely to exist. In this paper, we describe a novel randomized algorithm for exact radius computation in weighted digraphs with an expected running time in Õ(d³m) where d is the so-called combinatorial dimension. Our methodology is inspired by Clarkson’s algorithm for LP-type problems. The value of d denotes the size of a basis, which is a smallest subset of nodes which enforce the same radius as the whole node set. While we show that there exist graphs with d ∈ Θ(n), our empirical analysis reveals that even large real-world graphs have small combinatorial dimension. This allows us to compute the radius in near-linear time on such instances. The significantly improved scalability can be clearly observed in our experimental evaluation on a diverse set of benchmark graphs.

Contraction Hierarchies (CH) are one of the most popular techniques for accelerating shortest path queries. In previous works, it has been shown that CH in principle can be instrumented to also produce variable level-of-detail renderings of road networks. Yet, the existing approach still suffers from severe drawbacks like topological inconsistencies or distortion of the overall shape of the road network, which impairs the practical usability. We significantly improve upon the existing approach both in terms of quality of the visual representation as well as query times. As a result, we obtain a lightweight augmentation of the CH data structure that allows for very efficient and visually pleasing rendering of massive road network data.

Most popular speed-up techniques for shortest path queries in road networks are based either on pruned graph search or clever lookup schemes and allow for answering of shortest path distance queries within continent-sized road networks in less than a milli-(search-based) or even microsecond (lookup-based) compared to several seconds of a normal Dijkstra run. While both paradigms previously have been considered mostly separately, we present a framework that unifies these seemingly different views on shortest path computations. Apart from the conceptual novelty, this allows for new and (practically very attractive) space-time tradeoffs for shortest-path computation. To our knowledge we are also the first to report on computational results for the largest connected component of the Open-StreetMap planet road network with more than half a billion nodes.

We present PATHFINDERVIS, a tool which is able to efficiently retrieve and visualize massive trajectory data on up to continent-sized networks. PATHFINDERVIS is an extension of the existing PATHFINDER framework which was designed as a pure backend and lacked a visualization. PATHFINDERVIS features many prototypes of different approaches to efficiently transmit and visualize large trajectory data.

In this paper, we consider the problem of gradual road network simplification, where given an embedded road network the goal is to compute a fine-grained succession of simplifications with decreasing level-of-detail. This allows to render the network on any desired zoom level or with a user-defined number of segments. Previous work has established that this can be achieved based on a Contraction Hierarchies (CH) data structure. CH was originally developed as a graph preprocessing method to speed up shortest path planning in road networks. However, since it is inherently based on a graph simplification mechanism, it can also serve as a basis for rendering. But the existing method exhibits several shortcomings, for example, topological inconsistencies arise on many simplification levels and the preservation of the shape of routes and the overall network for coarser graph representations is insufficient. This severely impairs the navigability of the map. We significantly improve upon the existing method by modifying the CH construction process as well as the rendering algorithm.

In a road network with multicriteria edge costs we consider the problem of computing a minimum number of driving preferences such that a given set of paths/trajectories is optimal under at least one of these preferences. While the exact formulation and solution of this problem appears theoretically hard, we show that in practice one can solve the problem exactly even for non-homeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also present a parameterized guaranteed-polynomial-time scheme with very good practical performance.

Given an ordered sequence of points P = {p₁, p₂, … , p_n}, we are interested in computing T, the set of distinct triangles occurring over all Delaunay triangulations of contiguous subsequences within P. We present a deterministic algorithm for this purpose with near-optimal time complexity O(|T|log n). Additionally, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles occurring over all contiguous subsequences is Θ(nlog n).

In this paper, we study a problem from the realm of multicriteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S0 with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S0. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.

We consider the problem of computing a set of alternative routes in a multicriteria setting where several network metrics are available. Previous approaches for alternative route computation were based on relaxing a single metric to obtain alternative routes whereas our approach for the multicriteria setting produces routes that are always optimal for a convex combination of the metrics. For the concrete example of route planning for bicycles with three natural metrics (distance, positive height difference, unsuitability for cycling) we show. how to efficiently generate very natural alternative bicycle routes.

In this paper, we study a problem from the realm of multi-criteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S' with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S'. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.

We consider the problem of indexing massive trajectory data in an underlying road network. Our Pathfinder index structure is based on a state-of-the-art speed-up technique for shortest path planning and allows to both compress and access huge amounts of trajectory data. In a continent-sized network with more than 400 million nodes and almost a billion edges, Pathfinder allows to retrieve all trajectories within a given space-time cube in a few microseconds per reported trajectory. The applicability of Pathfinder is shown using both synthetic and real-world trajectory sets.

Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in e.g. road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. But for many of these techniques it is not fully understood why they perform so remarkably well and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. But these parameters tend to be large (order of Θ(√n)) when the network contains grid-like substructures — which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. For graphs with a large highway or skeleton dimension, our results turn out to be superior. Furthermore, our preprocessing methods are close to the ones used in practice and only require randomized polynomial time.

We present CYCLOPS, a route planning system for cyclists that allows for intuitive specification of preferences for a route query, and also suggests several alternative route options. It combines three metrics of the underlying road network relevant to cyclists (distance, positive height gain, unsuitability for cycling), to cater for different cycling habits. The CYCLOPS back end is based on state-of-the-art multi-criteria route planning techniques, the front end is realized using the HTML5 Canvas API to provide an intuitive interface for combining metrics in personalized route planning queries and a visualization of the routes found.

A grid maze is a binary matrix where fields containing a 0 are accessible while fields containing a 1 are blocked. A movement sequence consists of relative movements up, down, left, right – moving to a blocked field results in non-movement. The simultaneous maze solving problem asks for the shortest movement sequence starting in the upper left corner and visiting the lower right corner for all mazes of size n × m (for which a path from the upper left to the lower right corner exists at all). We present a theoretical problem analysis, including hardness results and a cubic upper bound on the sequence length. In addition, we describe several approaches to practically compute solving sequences and lower bounds despite the high combinatorial complexity of the problem.

Given a set of prioritized balls with fixed centers in ℝd whose radii grow linearly over time, we want to compute the elimination order of these balls assuming that when two balls touch, the one with lower priority is ‘crushed’. A straightforward algorithm has running time O(n2 log n) which we improve to expected O(Δdn(log n + Δd)) where Δ = rmax/rmin is the ratio between largest and smallest radius amongst the balls. For a natural application of this problem, namely drawing labels on the globe, we have Δ = O(1). An efficient implementation based on a spherical Delaunay triangulation allows to compute the elimination order for millions of labels on commodity Desktop hardware. Dealing with rounding error induced robustness issues turned out to be one of the major challenges in the implementation.

We consider the classical line simplification problem subject to a given error bound ∊ but with additional topology constraints as they arise for example in the map rendering domain. While theoretically inapproximability has been proven for these problem variants, we show that in practice one can solve medium sized instances optimally using an integer linear programming approach and larger instances using an heuristic approach which for medium-sized real-world instances yields close-to-optimal results. Our approaches are evaluated on data sets which are synthetically generated, stem from the OpenStreetMap project[1], and the recent GISCup competition [3].

We consider the problem of indexing the complete OpenStreetMap planet data set (> 500GB of raw data) to support complex queries involving both text search as well as context-aware spatial relations. This requires (a) formalization of spatial relations like 'north of', 'between', 'near' depending on the context, and (b) the development of suitable data representations to integrate textual and spatial information for efficient query performance.

We consider the problem of generating concise and robust driving directions that avoid overly detailed turn-by-turn instructions as long as one is not too close to the final destination. Our approach is based on a deliberate selection of cities as landmarks that are likely to appear on road signs along the route. For a route from Stuttgart to Flensburg, the route description could read "Go towards Frankfurt, then Kassel, then Hanover, then Hamburg". Apart from being more compact, such driving directions are also more robust against wrong turns taken. While an implementation based on Dijkstra's algorithm takes on the order of several seconds to generate such driving directions, a careful instrumentation of speed-up techniques reduces this to fractions of a second required, e.g., for a web service.

In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.

We study the problem of learning individual route preferences of drivers. Most current route planning services only compute shortest or quickest paths. But many other criteria might play a role for a user to prefer a certain route, as, e.g., fuel consumption, jam likeliness, road conditions, scenicness of the route, turns, allowed maximum speeds, toll costs and many more. Specifying the importance of each criterion manually is a non-trivial, unintuitive and time consuming undertaking for a user. Therefore, we develop approaches that deduce such preferences automatically based on paths previously driven by the user. We present an LP-formulation of the problem making use of a Dijkstra-based separation oracle. The resulting algorithm runs in polynomial time and allows for the user preference computation in few seconds even if several hundred routes are taken into account. Our experiments show that new route suggestions based on these learned preferences reflect the users definition of an optimal route very well.

Often, the edge weights of graphs are given in implicitly infinite or overly high precision (think of Euclidean lengths) which leads to both theoretical as well as practical challenges. In this paper we investigate how to round edge weights of a given graph G(V,E,w) such that the rounded weights of paths satisfy certain consistency criteria. Natural consistency criteria are, for example, preserving optimality of paths, and bounding relative change in weight after the rounding procedure. Low precision edge weights allow for more space efficient implementations, faster arithmetic operations, and in general more stable and efficient algorithms. We present an ILP based rounding approach as well as a greedy rounding heuristic. We show experimentally for large road networks and grid graphs that our new rounding approaches are significantly better than common deterministic or randomized rounding schemes.

Computing shortest paths in road networks with millions of nodes and edges is challenging on its own. In the last few years, several preprocessing-based acceleration techniques have been developed to enable query answering orders of magnitudes faster than a plain Dijkstra computation. But most of these techniques work only if the metric which determines the optimal path is static or rarely changes. In contrast to that, we aim at answering personalized route planning queries. Here, every single query comes with a specification of its very own metric. This increases the combinatorial complexity of the problem significantly. We develop new preprocessing schemes that allow for real-time personalized route planning in huge road networks while keeping the memory footprint of the preprocessed data and subsequent queries small.

Compared to conventional cars, electric vehicles (EVs) still suffer from considerably shorter cruising ranges. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible so that on any shortest path there are sufficiently many not to run out of energy. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.

Compared to conventional cars, electric vehicles still suffer from a considerably shorter cruising range. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible such that on any shortest path there are enough to guarantee sufficient energy supply. This means, that EV owners no longer have to plan their trips ahead incorporating loading station locations, and are no longer forced to accept long detours to reach their destinations. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.

Frontmatter, Table of Contents, Preface, Workshop Organization

For a directed graph G with vertex set V we call a subset C ⊆ V a k-(All-)Path Cover if C contains a node from any path consisting of k nodes. This paper considers the problem of constructing small k -Path Covers in the context of road networks with millions of nodes and edges. In many application scenarios the set C and its induced overlay graph constitute a very compact synopsis of G which is the basis for the currently fastest data structure for personalized shortest path queries, visually pleasing overlays of subsampled paths, and efficient reporting, retrieval and aggregation of associated data in spatial network databases. Apart from a theoretical investigation of the problem, we provide efficient algorithms that produce very small k -Path Covers for large real-world road networks (with a posteriori guarantees via instance-based lower bounds).

The short cruising range due to the limited battery supply of current Electric Vehicles (EVs) is one of the main obstacles for a complete transition to E-mobility. Until batteries ofhigher energy storage density have been developed, it is of utmost importance to deliberately plan the locations of new loading stations for best possible coverage. Ideally the network of loading stations should allow driving from anywhere to anywhere (and back) without running out of energy. We show that minimizing the number of necessary loading stations to achieve this goal is NP-hard and even worse, we can rule out polynomial-time constant approximation algorithms. Hence algorithms with better approximation guarantees have to make use of the special structure of road networks (which is not obvious how to do it). On the positive side, we show with instance based lower bounds that our heuris-tic algorithms achieve provably good solutions on real-world problem instances.

We consider multicriteria shortest path problems and show that contraction hierarchies — a very powerful speed-up technique originally developed for standard shortest path queries in [7] — can be constructed efficiently for the case of arbitrary conic combinations of the edge costs. This extends previous results in [5] which considered only the bicriteria case and discrete weights for the objective functions. On the theory side we prove a polynomial time bound for determining whether a path π is part of the lower envelope of all pareto-optimal paths via some polyhedral arguments. Experiments complement these results by showing the practicability of our approach.

In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) — a very powerful speed-up technique originally developed for standard shortest path queries (Geisberger et al. 2008) — can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case. This is an extended abstract of the full paper published in (Funke and Storandt 2013).

The main hindrance to a widespread market penetration of battery-powered electric vehicles (BEVs) has been their limited energy reservoir resulting in cruising ranges of few hundred kilometers unless one allows for recharging or switching of depleted batteries during a trip. Unfortunately, recharging typically takes several hours and battery switch stations providing fully recharged batteries are still quite rare – certainly not as widespread as ordinary gas stations. For not getting stranded with an empty battery, going on a BEV trip requires some planning ahead taking into account energy characteristics of the BEV as well as available battery switch stations. In this paper we consider very basic, yet fundamental problems for E-Mobility: Can I get from A to B and back with my BEV without recharging in between? Can I get from A to B when allowed to recharge? How can I minimize the number of battery switches when going from A to B? We provide efficient and mathematically sound algorithms for these problems that allow for the energy-aware planning of trips.

We reconsider the concept of transit nodes as introduced by Bast et al. [3] and for the first time construct instance based lower bounds on the size of transit node sets by interpreting a LP formulation of the problem and its dual. As a side product we achieve considerably smaller access node sets which directly influences the query time for non-local queries.

When heading back home from work there are often things to do on the way like grocery shopping, getting cash from an ATM, refueling at a gas station, or dropping off a parcel at a post-office. We consider the problem of planning an optimal route (quickest or shortest) that visits facilities of the respective type on the way home. The proposed solution based on the combination of a distance sensitive doubling technique and contraction hierarchies is orders of magnitudes faster than either a naive approach or previous results and produces the answers in an instant for realistic queries without compromising guaranteed optimality. With such fast query times, this type of route query becomes feasible even on mobile devices or for high-throughput web-based route planners.

We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under non-constant edge costs we obtain O(n log n +m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation.If the energy recuperation is height induced in a very natural way,the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.

We consider the following two problems: Map Matching: Given a sequence of (imprecise) location measurements from a mobile user moving on a road network, determine the most likely path in the network this user has travelled along. Prediction of Trajectories: Given the path of where a mobile user has moved along in a road network up to now, predict where he will travel along in the near future. Our map matching algorithm is simple and efficient even in case of very imprecise measurements like GSM-localizations and allows for the real-time tracking of a large number of mobile users on modest hardware. Our proposed path prediction algorithm is equally simple but yields extremely accurate predictions at a very low computational cost.

We propose a novel scheme for map matching and fully autonomous self-localization. Our scheme is based on the unique characteristics of the shape of paths in a road network. As uniqueness of path shapes comes as no surprise in a world of infinite precision, we develop robust means of comparing shapes of paths under imprecisions. Even under this fuzzy comparison model, path shapes turn out to be sufficiently characteristic to allow for map matching or fully autonomous self-localization. We design an efficient data structure which allows for very fast path shape queries.

Known algorithms for reconstructing a 2-manifold from a point sample in ℝ3 are naturally based on decisions/predicates that take the geometry of the point sample into account. Facing the always present problem of round-off errors that easily compromise the exactness of those predicate decisions, an exact and robust implementation of these algorithms is far from being trivial and typically requires the employment of advanced datatypes for exact arithmetic as provided by libraries like CORE, LEDA or GMP. In this paper we present a new reconstruction algorithm, one of whose main novelties is to throw away geometry information early on in the reconstruction process and to mainly operate combinatorially on a graph structure. As such it is less susceptible to robustness problems due to round-off errors and also benefits from not requiring expensive exact arithmetic by faster running times. A more theoretical view on our algorithm including correctness proofs under suitable sampling conditions can be found in a companion paper [3].

When you drive to somewhere 'far away', you will leave your current location via one of only a few 'important' traffic junctions.Starting from this informal observation, we develop an algorithmic approach-transit node routingthat allows us to reduce quickest-path queries in road networks to a small number of table lookups.We present two implementations of this idea, one based on a simple grid data structure and one based on highway hierarchies.For the road map of the United States, our best query times improve over the best previously published figures by two orders of magnitude.Our results exhibit various trade-offs between average query time (5 µs to 63 µs), preprocessing time (59 min to 1200 min), and storage overhead (21 bytes/node to 244 bytes/node).

Geographic routing protocols like GOAFR or GPSR rely on exact location information at the nodes, as when the greedy routing phase gets stuck at a local minimum, they require, as a fallback, a planar subgraph whose identification, in all existing methods, depends on exact node positions. In practice, however, location information at the network nodes is hardly precise; be it because the employed location hardware, such as GPS, exhibits an inherent measurement imprecision, or because the localization protocols which estimate positions of the network nodes cannot do so without errors. In this paper we propose a novel naming and routing scheme that can handle the uncertainty in location information. It is based on a macroscopic variant of geographic greedy routing, as well as a macroscopic planarization of the communication graph. If an upper bound on the deviation from true node locations is available, our routing protocol guarantees delivery of messages. Due to its macroscopic view, our routing scheme also produces shorter and more load-balanced paths than common geographic routing schemes, in particular in sparsely connected networks or in the presence of obstacles.

Wireless sensor networks typically consist of small, very simple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly, but have no idea about their relative geographic locations. We examine how much geometry information is nevertheless hidden in the communication graph of the network: Assuming that the connectivity is determined by the well-known unit-disk graph model, we prove that using an extremely simple linear-time algorithm one can identify nodes on the boundaries of holes of the network. That is, there is enough geometry information hidden in the connectivity structure to identify topological features—in our example the holes in the network. While the theoretical analysis turns out to be quite conservative,an actual implementation shows that the algorithm works well under less stringent conditions.

Consider the following illumination problem: given a stage represented by a line segment L and a set of lightsources represented by a set of points S in the plane, assign powers to the lightsources such that every point on the stage receives a sufficient amount -- let's say one unit -- of light while minimizing the overall power consumption. By assuming that the amount of light arriving from a fixed lightsource decreases rapidly with the distance from the lightsource, this becomes an interesting optimization problem.We propose to reconsider the classical illumination problems as known from computational geometry literature (e.g. [12]) under this light attenuation model. This paper examines the simple problem introduced above and presents different solutions, based on convex optimization, discretization and linear programming, as well as a purely combinatorial approximation algorithm. Some experimental results are also provided.

In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure.No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constraints imposed by the chosen grid.In this paper we present a new approach which combines the grid-based combinatorial method with Simulated Annealing on a continuous model. This allows us to explore arbitrary orientations and placements of boxes, hence closing the gap even further, and - in some cases - even surpass the manual expert solution.The implemented software system allows our industrial partner to incorporate the trunk volume in a very early stage of the car design process without relying on a repeated and cumbersome manual evaluation of the volume.

Several routing schemes in ad hoc networks first establish a virtual backbone and then route messages via backbone nodes. One common way of constructing such a backbone is based on the construction of a connected dominating set (CDS). In this article we present a very simple distributed algorithm for computing a small CDS. Our algorithm has an approximation factor of at most 6.91, improving upon the previous best-known approximation factor of 8 due to Wan et al. [2002]. The improvement relies on a refined analysis of the relationship between the size of a maximal independent set and a minimum CDS in a unit disk graph. This subresult also implies improved approximation factors for many existing algorithm.

We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic algorithm was presented, but only a heuristic implementation with no guarantee was practicable. We present a new approximation algorithm for the problem which runs in O(n∈2) time and---apart from giving a guarantee on the quality of the produced solution---has been implemented and shows good performance on real data sets representing fracture surfaces consisting of around half a million triangles. Further we present a simple approximation algorithm for a related problem: given a set of n points in the plane, determine the placement of the unit disc which contains most points. This algorithm runs in linear time as well.

We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases.We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k -th root operations for integral k , and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real .

In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the exact number types provided by LEDA allowing for efficient and exact computation with rational and algebraic geometric objects. It is the first kernel design which uses floating-point filter techniques on the level of geometric constructions. The experiments we present -- partly using the CGAL framework -- show a great improvement in speed and -- maybe even more important for practical applications -- memory consumption when dealing with more complex geometric computations.

In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision packages, we develop an easy-to-use expression compiler called EXPCOMP. EXPCOMP supports all common operations +; \\Gamma; \\Delta; =; p . Applying a new semi-static filter, EXPCOMP combines the speed of static filters with the power of dynamic filters. The filter stages deal with all kinds of floating-point exceptions, including underflow. The resulting programs show a very good runtime behaviour. 1 Introduction When computer scientists design geometric algorithms, they usually assume the availability of exact arithmetic on real numbers. Since no computer directly provides exact arithmetic on real numbers, programmers implementing these algorithms must find some substitution. Quite commonly, they resort to floating-point arithmetic due to its support by hardand software as well as its co...