We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with m edges these values can be computed in roughly O(m²) time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most k can be computed in O(n log^O(k) n) time, where n is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with n vertices and F faces takes O(n F log n) time.

Abstract The farthest-color Voronoi diagram (FCVD) is defined on a set of n points in the plane, where each point is labeled with one of m colors. The colored points constitute a family $$\mathcal {P}$$ P of m clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is $$O(n\alpha (m)+\textit{str}(\mathcal {P}))$$ O ( n α ( m ) + str ( P ) ) , where $$\textit{str}(\mathcal {P})$$ str ( P ) is a parameter reflecting the number of straddles between pairs of clusters, which is $$O(m(n-m))$$ O ( m ( n - m ) ) . The bound reduces to $$O(n+ \textit{str}(\mathcal {P}))$$ O ( n + str ( P ) ) if the clusters are pairwise non-crossing . We also present a lower bound, establishing that the complexity of the FCVD can be $$\Omega (n+m^2)$$ Ω ( n + m 2 ) , even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in $$O((n+\textit{str}(\mathcal {P}))\log ^3 n)$$ O ( ( n + str ( P ) ) log 3 n ) -time, and in certain special cases in $$O(n\log n)$$ O ( n log n ) time.

Abstract We study a geometric facility location problem under imprecision. Given n unit segments on the real line, each with one of k colors, the goal is to place a point on each segment such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in O ( n ) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in $$O(n \log ^2 n)$$ O ( n log 2 n ) time when $$k=2$$ k = 2 , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.

We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s,t), which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s,t), which is an any-angle shortest path; and a weighted shortest grid path SGPw(s,t), which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios ‖SGPw(s,t)‖‖SPw(s,t)‖, ‖SVPw(s,t)‖‖SPw(s,t)‖, ‖SGPw(s,t)‖‖SVPw(s,t)‖, which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that ‖SGPw(s,t)‖‖SPw(s,t)‖=23≈1.15 in the worst case, and this is tight. As a corollary, for the weighted any-angle path SVPw(s,t) we obtain the approximation result ‖SVPw(s,t)‖‖SPw(s,t)‖⪅1.15.

We study the problem of constructing a data structure that can store a two-dimensional polygonal curve $P$, such that for any query segment $\overline{ab}$ one can efficiently compute the Fréchet distance between $P$ and $\overline{ab}$. First we present a data structure of size $O(n \log n)$ that can compute the Fréchet distance between $P$ and a horizontal query segment $\overline{ab}$ in $O(\log n)$ time, where $n$ is the number of vertices of $P$. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment $\overline{ab}$ together with two points $s, t \in P$ (not necessarily vertices), and ask for the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$. Using $O(n\log^2n)$ storage, such queries take $O(\log^3 n)$ time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an $O(nk^{3+\varepsilon}+n^2)$ size data structure, where $k \in [1..n]$ is a parameter the user can choose, and $\varepsilon > 0$ is an arbitrarily small constant, such that given any segment $\overline{ab}$ and two points $s, t \in P$ we can compute the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$ in $O((n/k)\log^2n+\log^4 n)$ time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments. We also present two applications of our data structure: we show that we can compute a local $δ$-simplification (with respect to the Fréchet distance) of a polygonal curve in $O(n^{5/2+\varepsilon})$ time, and that we can efficiently find a translation of an arbitrary query segment $\overline{ab}$ that minimizes the Fréchet distance with respect to a subcurve of $P$.

The automatic generation of road networks from GPS tracks is a challenging problem that has been receiving considerable attention in the last years. Although dozens of methods have been proposed, current techniques suffer from two main shortcomings: the quality of the produced road networks is still far from those produced manually, and the methods are slow, making them not scalable to large inputs. In this paper, we present a fast four-step density-based approach to construct a road network from a set of trajectories. A key aspect of our method is the use of an improved version of the Slide method to adjust trajectories to build a more compact density surface. The network has comparable or better quality than that of state-of-the-art methods and is simpler (includes fewer nodes and edges). Furthermore, we also propose a split-and-merge strategy that allows splitting the data domain into smaller regions that can be processed independently, making the method scalable to large inputs. The performance of our method is evaluated with extensive experiments on urban and hiking data.

Let p and q be two imprecise points, given as probability density functions on $$\mathbb {R} ^2$$ , and let $$\mathcal {O} $$ be a set of disjoint polygonal obstacles in $$\mathbb {R} ^2$$ . We study the problem of approximating the probability that p and q can see each other; i.e., that the segment connecting p and q does not cross any obstacle in $$\mathcal {O} $$ . To solve this problem, we first approximate each density function by a weighted set of polygons. Then we focus on computing the visibility between two points inside two of such polygons, where we can assume that the points are drawn uniformly at random. We show how this problem can be solved exactly in $$O((n+m)^2)$$ time, where n and m are the total complexities of the two polygons and the set of obstacles, respectively. Using this as a subroutine, we show that the probability that p and q can see each other amidst a set of obstacles of total complexity m can be approximated within error $$\varepsilon $$ in $$O(1/\varepsilon ^3+m^2/\varepsilon ^2)$$ time.

We propose a new approach for constructing the underlying map from trajectory data. Our algorithm is based on the idea that road segments can be identified as stable subtrajectory clusters in the data. For this, we consider how subtrajectory clusters evolve for varying distance values, and choose stable values for these. In doing so we avoid a global proximity parameter. Within trajectory clusters, we choose representatives, which are combined to form the map. We experimentally evaluate our algorithm on vehicle and hiking tracking data. These experiments demonstrate that our approach can naturally separate roads that run close to each other and can deal with outliers in the data, two issues that are notoriously difficult in road network reconstruction.

The Delaunay triangulation is the standard choice for building triangulated irregular networks (TINs) to represent terrain surfaces. However, the Delaunay triangulation is based only on the 2D coordinates of the data points, ignoring their elevation. It has long been recognized that sometimes it may be beneficial to use other, non-Delaunay, criteria to build TINs. Data-dependent triangulations were introduced decades ago to address this. However, they are rarely used in practice, mostly because the optimization of data- dependent criteria often results in triangulations with many thin and elongated triangles. Recently, in the field of computational geometry, higher order Delaunay triangulations (HODTs) were introduced, trying to tackle both issues at the same time-data-dependent criteria and good triangle shape. Nevertheless, most previous studies about them have been limited to theoretical aspects. In this work we present the first extensive experimental study on the practical use of HODTs, as a tool to build data-dependent TINs. We present experiments with two USGS terrains that show that HODTs can give significant improvements over the Delaunay triangulation for the criteria identified as most important for data-dependent triangulations. The resulting triangulations have data-dependent values comparable to those obtained with pure data-dependent approaches, without compromising the shape of the triangles, and are faster to compute.

We present a robust and compact meta-module for edge-hinged modular robot units such as M-TRAN, SuperBot, SMORES, UBot, PolyBot and CKBot, as well as for central-point-hinged ones such as Molecubes and Roombots. Thanks to the rotational degrees of freedom of these units, the novel meta-module is able to expand and contract, as to double/halve its length in each dimension. Moreover, for a large class of edge-hinged robots the proposed meta-module also performs the scrunch/relax and transfer operations required by any tunneling-based reconfiguration strategy, such as those designed for Crystalline and Telecube robots. These results make it possible to apply efficient geometric reconfiguration algorithms to this type of robots. We prove the size of this new meta-module to be optimal. Its robustness and performance substantially improve over previous results.

In this paper we present new geometric algorithms for approximating the visibility between two imprecise locations amidst a set of obstacles, where the imprecise locations are modeled by continuous probability distributions. Our techniques are based on approximating distributions by a set of regions rather than on approximating by a discrete point sample. In this way we obtain guaranteed error bounds, and the results are more robust than similar results based on discrete point sets. We implemented our techniques and present an experimental evaluation. The experiments show that the actual error of our region-based approximation scheme converges quickly when increasing the complexity of the regions.

In memory-constrained algorithms we have read-only access to the input, and the number of additional variables is limited. In this paper we introduce the compressed stack technique, a method that allows to transform algorithms whose space bottleneck is a stack into memory-constrained algorithms. Given an algorithm A that runs in O(n) time using a stack of length Theta(n), we can modify it so that it runs in O(n^2/2^s) time using a workspace of O(s) variables (for any s \in o(log n)) or O(n log n/log p)$ time using O(p log n/log p) variables (for any 2 <= p <= n). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach exceeds or matches the best-known results for these problems in constant-workspace models (when they exist), and gives a trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms.

We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in $O(n^{4/3}\operatorname{polylog}n)$ expected time, where $n$ is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a $(1+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain.

A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O(n 3)-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.

Spatially aggregated data is frequently used in geographical applications. Often spatial data analysis on aggregated data is performed in the same way as on exact data, which ignores the fact that we do not know the actual locations of the data. We here propose models and methods to take aggregation into account. For this we focus on the problem of locating clusters in aggregated data. More specifically, we study the problem of locating clusters in spatially aggregated health data. The data is given as a subdivision into regions with two values per region, the number of cases and the size of the population at risk. We formulate the problem as finding a placement of a cluster window of a given shape such that a cluster function depending on the population at risk and the cases is maximized. We propose area-based models to calculate the cases (and the population at risk) within a cluster window. These models are based on the areas of intersection of the cluster window with the regions of the subdivision. We show how to compute a subdivision such that within each cell of the subdivision the areas of intersection are simple functions. We evaluate experimentally how taking aggregation into account influences the location of the clusters found.

We study variants of the potato peeling problem on meshed (triangulated) polygons. Given a polygon with holes, and a triangular mesh that covers its interior (possibly using additional vertices), we want to find a largest-area connected set of triangles of the mesh that is convex, or has some other shape-related property. In particular, we consider (i) convexity, (ii) monotonicity, (iii) bounded backturn, and (iv) bounded total turning angle. The first three problems are solved in polynomial time, whereas the fourth problem is shown to be NP-hard.

Data conflation is a major issue in GIS: different geospatial datasets covering overlapping regions, possibly obtained from different sources and using different acquisition techniques, need to be combined into one single consistent dataset before the data can be analyzed. The most common occurrence for hydrological applications is conflation of a digital elevation model (DEM) and rivers. We assume that a triangulated irregular network (TIN) is given, and a subset of its edges are designated as river edges, each with a flow direction. The goal is to obtain a terrain where the rivers flow along valley edges, in the specified direction, while preserving the original terrain as much as possible. We study the problem of changing the elevations of the vertices to ensure that all the river edges become valley edges, while minimizing the total elevation change. We show that this problem can be solved using linear programming. However, several types of artifacts can occur in an optimal solution. We analyze which other criteria, relevant for hydrological applications, can be captured by linear constraints as well, in order to eliminate such artifacts. We implemented and tested the approach on real terrain and river data, and describe the results obtained with different variants of the algorithm.

We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D - polyhedral terrains - can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4/3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1+ε)-approximation algorithm for minimizing the area that runs in O(n/√ε) time, for any fixed ε > 0. The (1 + ε)- approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/ε2) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain.

We investigate the concept of a median among a set of trajectories. We establish criteria that a “median trajectory” should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worst-case running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and analyze whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better.

Data conflation is a major issue in GIS: spatial data obtained from different sources, using different acquisition techniques, needs to be combined into one single consistent data set before the data can be analyzed. The most common occurrence for hydrological applications is conflation of a digital elevation model and rivers. We assume that a polyhedral terrain is given, and a subset of its edges are designated as river edges, each with a flow direction. The goal is to obtain a terrain where the rivers flow along valley edges, in the specified direction, while preserving the original terrain as much as possible.

Road network data is often incomplete, making it hard to perform network analysis. This paper discusses the problem of extending partial road networks with reasonable links, using the concept of dilation (also known as crow flight conversion coefficient). To this end, we study how to connect a point (relevant location) inside a polygon (face of the known part of the road network) to the boundary so that the dilation from that point to any point on the boundary is not too large. We provide algorithms and heuristics, and give a computational and experimental analysis.