Search

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model \emph{braided rivers} (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a \emph{sand function} that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are $\delta$-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum $\delta$-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers., Journal of Computational Geometry, Vol. 10 No. 1 (2019)

We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

In the trajectory segmentation problem, we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment. To the best of our knowledge, no theoretical results are known for nonmonotone criteria. We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the start-stop diagram : a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (1) computing the start-stop diagram, and (2) finding the optimal segmentation for a given diagram. We show that (2) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable and give a polynomial-time algorithm for this case. We study two concrete nonmonotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function f over the domain of the trajectory. We say a segment satisfies an outlier-tolerant criterion if the value of f lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a standard deviation criterion if the standard deviation of f over the length of the segment lies below a given threshold. We show that both criteria satisfy the properties that make the segmentation problem tractable. In particular, we compute an optimal segmentation of a trajectory based on the outlier-tolerant criterion in O ( n 2 log n + kn 2 ) time and on the standard deviation criterion in O ( kn 2 ) time, where n is the number of vertices of the input trajectory and k is the number of segments in an optimal solution.

In this paper we introduce several innovative variants on the classic Connect-The-Dots puzzle. We study the underlying geometric principles and investigate methods for the automatic generation of high-quality puzzles from line drawings. Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging "game play", making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy. Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle --one satisfying the mentioned criteria-- is computationally hard, and present several heuristic algorithms. Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.

Two of the grouping definitions for trajectories that have been developed in recent years allow a continuous motion model and allow varying shape groups. One of these definitions was suggested as a refinement of the other. In this paper we perform an experimental comparison to highlight the differences in these two definitions on various data sets.

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.

Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-Approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-Time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.

We present a framework for designing shapes from diverse combinatorial patterns, where the vertex 1-rings and the faces are as rotationally symmetric as possible, and define such meshes as regular. Our algorithm computes the geometry that brings out the symmetries encoded in the combinatorics. We then allow designers and artists to envision and realize original meshes with great aesthetic qualities. Our method is general and applicable to meshes of arbitrary topology and connectivity, from triangle meshes to general polygonal meshes. The designer controls the result by manipulating and constraining vertex positions. We offer a novel characterization of regularity, using quaternionic ratios of mesh edges, and optimize meshes to be as regular as possible according to this characterization. Finally, we provide a mathematical analysis of these regular meshes, and show how they relate to concepts like the discrete Willmore energy and connectivity shapes.

The 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.

Movement data comes in various forms, including trajectory data and checkpoint data. While trajectories give detailed information about the movement of individual entities, checkpoint data in its simplest form does not give identities, just counts at checkpoints. However, checkpoint data is of increasing interest since it is readily available due to privacy reasons and as a by-product of other data collection. In this paper we propose to use the Earth Mover’s Distance as a versatile tool to reconstruct individual movements or flow based on checkpoint counts at different times. We analyze the modeling possibilities and provide experiments that validate model predictions, based on coarse-grained aggregations of data about actual movements of couriers in London, UK. While we cannot expect to reconstruct precise individual movements from highly granular checkpoint data, the evaluation does show that the approach can generate meaningful estimates of object movements. B. Speckmann and K. Verbeek are supported by the Netherlands Organisation for Scientific Research (NWO) under project nos. 639.023.208 and 639.021.541, respectively. This paper arose from work initiated at Dagstuhl seminar 12512 “Representation, analysis and visualization of moving objects”, December 2012. The authors gratefully acknowledge Schloss Dagstuhl for their support.

An important task in trajectory analysis is defining a meaningful representative for a cluster of similar trajectories. Formally defining and computing such a representative r is a challenging problem. We propose and discuss two new definitions, both of which use only the geometry of the input trajectories. The definitions are based on the homotopy area as a measure of similarity between two curves, which is a minimum area swept by all possible deformations of one curve into the other. In the first definition we wish to minimize the maximum homotopy area between r and any input trajectory, whereas in the second definition we wish to minimize the sum of the homotopy areas between r and the input trajectories. For both definitions computing an optimal representative is NP-hard. However, for the case of minimizing the sum of the homotopy areas, an optimal representative can be found efficiently in a natural class of restricted inputs, namely, when the arrangement of trajectories forms a directed acyclic graph.

We define the notion of disk-obedience for a set of disks in the plane and give results for disk-obedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.

An 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 $\mathcal{C}$, 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 $t$, the point $\mathcal{C}(t)$ is as central as possible. We measure centrality in terms of the radius of the smallest disk centered at $\mathcal{C}(t)$ enclosing all entities at time $t$, and discuss how the techniques can be adapted to other measures of centrality. We first study the problem in $\mathbb{R}^1$, where we show that an optimal central trajectory $\mathcal{C}$ representing $n$ trajectories, each consisting of $\tau$ edges, has complexity $\Theta(\tau n^2)$ and can be computed in $O(\tau n^2 \log n)$ time. We then consider trajectories in $\mathbb{R}^d$ with $d\geq 2$, and show that the complexity of $\mathcal{C}$ is at most $O(\tau n^{5/2})$ and can be computed in $O(\tau n^3)$ time., Comment: Full version

Route memory is frequently assessed in virtual environments. These environments can be presented in a fully controlled manner and are easy to use. Yet they lack the physical involvement that participants have when navigating real environments. For some aspects of route memory this may result in reduced performance in virtual environments. We assessed route memory performance in four different environments: real, virtual, virtual with directional information (compass), and hybrid. In the hybrid environment, participants walked the route outside on an open field, while all route information (i.e., path, landmarks) was shown simultaneously on a handheld tablet computer. Results indicate that performance in the real life environment was better than in the virtual conditions for tasks relying on survey knowledge, like pointing to start and end point, and map drawing. Performance in the hybrid condition however, hardly differed from real life performance. Performance in the virtual environment did not benefit from directional information. Given these findings, the hybrid condition may offer the best of both worlds: the performance level is comparable to that of real life for route memory, yet it offers full control of visual input during route learning.

We introduce a method for automatically rating the difficulty of puzzle game levels. Our method takes multiple aspects of the levels of these games, such as level size, and combines these into a difficulty function. It can simply be adapted to most puzzle games, and we test it on three different ones: Flow, Lazors and Move. We conducted a user study to discover how difficult players find the levels of a set and use this data to train the difficulty function to match the user-provided ratings. Our experiments show that the difficulty function is capable of rating levels with an average error of approximately one point in Lazors and Move, and less than half a point in Flow, on a difficulty scale of 1-10.

A variety of recurring geographic entities form collections of point, line, or area features. Examples are groups of islands (Archipelago), relief features in deserts, periglacial lakes or geomorphological forms, such as drumlins and sinkholes. All these groups of features might be best identified with a single label. Surprisingly, the (automated) labeling of groups of features has received little attention so far. We propose a framework to determine formal measures that describe the geometric aspects of the cartographic design space for labeling feature groups. Our framework gives rise to a large variety of geometrically optimal labels. We list the optimal label positions and shapes for which labels can already be computed using existing algorithms. However, in many of the cases computing optimal label placements is still an open algorithmic question which can readily be investigated in future work. Once the necessary algorithms are developed, our framework provides an objective basis to investigate the geometric measures used by cartographers to label groups of features. We preliminarily explore the applicability of our framework using one of the geometric optimality choices. Keywords: automated cartography, labeling, groups of features

We consider two variants of the fundamental question of determining whether a simply connected flexible combinatorial structure can be realized in Euclidean space. Two models are considered: body-and-joint frameworks and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage (body-and-bar framework) is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles; but efficiently decidable for a chain of triangles hinged at distinct vertices. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane.

In Lombardi drawings of graphs, edges are represented as circular arcs and the edges incident on vertices have perfect angular resolution. However, not every graph has a Lombardi drawing and not every planar graph has a planar Lombardi drawing. We introduce k-Lombardi drawings, in which each edge may be drawn with k circular arcs; we show that every graph has a smooth 2-Lombardi drawing and every planar graph has a smooth planar 3-Lombardi drawing. We also investigate related topics connecting planarity and Lombardi drawings.

We present a list of measures for a single trajectory, including measures that require the presence of other trajectories, such as the centrality of a trajectory amidst other trajectories. Then, we introduce three different views in order to extend measures of a single trajectory to a group, namely the representative view, the complete view and the area view. Furthermore, we give measures that exist only for a group of trajectories, like density and formation stability. We also show that it may be possible to define new measures by combining trajectory data with data from other sources, such as the environment where the entities move. Finally, we discuss several tasks: settlement selection, visualization and segmentation, where measures on groups of trajectories are necessary.

We 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(log⁡n) , and local updates in time O(logn/loglogn)O(log⁡n/log⁡log⁡n) , 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.

In this paper we study the following problem: we are given a set of imprecise points modeled as parallel line segments, and we wish to place three points in different regions such that the resulting triangle has the largest or smallest possible area. We first present some facts about this problem in the context of imprecise points, then we show that for a given set of line segments of equal length the largest possible area triangle can be found in $O(n log n)$ time, and for line segments of arbitrary length the problem can be solved in $O(n^2)$ time. We also show that the smallest possible area triangle for a set of arbitrary length parallel line segments can be found in $O(n^2)$ time.

For both the Fréchet distance and the symmetric difference, we show that finding the simple polygon $S$ restricted to a grid that best resembles a simple polygon $P$ is NP-complete, even if: (1) we require that $S$ and $P$ have equal area; (2) we require turns to occur in a specified sequence for the Fréchet distance; (3) we permit $S$ to have holes for the symmetric difference.

With Google Scholar, scientists can maintain their publications on personal profile pages, while the citations to these works are automatically collected and counted. Maintenance of publications is done manually by the researcher herself, and involves deleting erroneous ones, merging ones that are the same but which were not recognized as the same, adding forgotten co-authors, and correcting titles of papers and venues. The publications are presented on pages with 20 or 100 papers in the web page interface from 2012-2014. (Since mid 2014, Google Scholar's profile pages allow any number of papers on a single page.) The interface does not allow a scientist to merge two versions of a paper if they appear on different pages. This not only implies that a scientist who wants to merge certain subsets of publications will sometimes be unable to do so, but also, we show in this note that the decision problem to determine if it is possible to merge given subsets of papers is NP-complete. We define the Google Scholar Merge Problem after the user interface used on the profile pages of Google Scholar.We prove that the Google Scholar Merge Problem is NP-complete by reduction from 3-partition.We list open problems that are variations of the Google Scholar Merge Problem.

We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given ε > 0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most ε. We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than we require for the optimum solution. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the (continuous) Fréchet distance, we give an $O(kn^5)$ time algorithm that requires $O(kn^2)$ space, where $k$ is the output complexity of the simplification., Journal of Computational Geometry, Vol. 11 No. 1 (2020)

To alleviate the problem that only a single polygonal line can be drawn to solve the puzzle, we allow interruptions by using two point symbols instead of just one. If the label of a dot is a normal number, then the edge to the next highernumbered point should be drawn, but if the label has a “+” appended to it, then the next edge should not be drawn. In this way the puzzler draws several polygonal lines. By giving a point more than one label, junctions can be made as well. ∗Department of Computing and Information Sciences, Utrecht University; Utrecht, the Netherlands; m.kaiser@students.uu.nl, {timvankapel,gerwin.klappe}@gmail.com, {m.j.vankreveld,m.loffler,f.staals}@uu.nl. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for thirdparty components of this work must be honored. For all other uses, contact the Owner/Author.

Introduction. In recent years there has been an increase in locationaware devices and wireless communication networks. This has led to a large amount of trajectory data capturing the movement of animals, vehicles, and people. The increase in trajectory data goes hand in hand with an increasing demand for techniques and tools to analyze them, for example, in transportation sciences, sports, ecology, and social services. An important task is the analysis of movement patterns. In particular, given a set of moving entities we wish to determine when and which subsets of entities travel together. When a sufficiently large set of entities travels together for a sufficiently long time, we call such a set a group. Groups may start, end, split and merge with other groups. Apart from the question what the current groups are, we also want to know which splits and merges led to the current groups, when they happened, and which groups they involved. We wish to capture this group change information in a model that we call the trajectory grouping structure.

We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph $GK_n$ on any set $S$ of $n$ points in general position in the plane? We show that this number is in $\Omega(\sqrt{n})$. Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths)., Comment: This work was presented at the 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax, Nova Scotia, Canada, 2014. The journal version appeared in Information Processing Letters, 124 (2017), 35--41

One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al.2 introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R1, specified by linear interpolation in a sequence of τ time stamps, we show that all maximal groups can be computed in O(τ2n4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of α(n) in the running time, where α denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in O(τ2n5logn) time (for any constant number of dimensions), regardless of whether the time stamps of entities are the same or not. We also show that one τ factor can be traded for a much higher dependence on n by giving a O(τn42n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on nand linear dependence on τ.

Many algorithmic results are known for automated label placement on maps. However, algorithms to compute labels for groups of features, such as island groups, are largely missing. In this paper we address this issue by presenting new, efficient algorithms for island label placement in various settings. We consider straight-line and circular-arc labels that may or may not overlap a given set of islands. We concentrate on computing the line or circle that minimizes the maximum distance to the islands, measured by the closest distance. We experimentally test whether the generated labels are reasonable for various real-world island groups, and compare different options. The results are positive and validate our geometric formalizations.

Motivated 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 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.

We define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to determine whether a given graph has a strict confluent drawing but polynomial to determine whether it has an outerplanar strict confluent drawing with a fixed vertex ordering (a drawing within a disk, with the vertices placed in a given order on the boundary).

We study a problem proposed by Hurtado et al. [10] motivated by sparse set visualization. Given n points in the plane, each labeled with one or more primary colors, a colored spanning graph (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The Min-CSG problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for k primary colors when \(k\ge 3\) and provide a \((2-\frac{1}{3+2\varrho })\)-approximation algorithm for \(k=3\) that runs in polynomial time, where \(\varrho \) is the Steiner ratio. Further, we give a O(n) time algorithm in the special case that the input points are collinear and k is constant.

Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles the bounding boxes of the label texts. Typically, labeling models either use internal labels, which must touch their feature point, or external boundary labels, which are placed on one of the four sides of the input points' bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation $$\theta \in [0,2\pi $$, whose value influences the geometric properties and hence the running times of our algorithms.