We define a graph tile to be a unit square (or more generally, a polygon) on which a piece of a graph has been drawn/embedded; in particular, it may have vertices in its interior, edges connecting those vertices, or half-edges that extend to the boundary of the tile. In a graph tiling problem, we are given as input a set of graph tiles, with multiplicities, and the output is an arrangement of those tiles forming a graph of larger area. We focus on a simple tile set: unit square tiles with a central vertex and either a half-edge or no half-edge on each side. Up to symmetry this gives us six different types. We characterize which multiplicities are compatible for sets of at most three different tiles.

Understanding individual human mobility is critical for a wide range of applications. Real-world trajectory datasets provide valuable insights into actual movement behaviors but are often constrained by data sparsity and participant bias. Synthetic data, by contrast, offer scalability and flexibility but frequently lack realism. To address this gap, we introduce a comprehensive software pipeline for generating, calibrating, and processing large-scale human mobility datasets that integrate the realism of empirical data with the control and extensibility of Patterns-of-Life simulations. Our system consists of three integrated components. First, a genetic algorithm-based calibration module fine-tunes simulation parameters to align with real-world mobility characteristics, such as daily trip counts and radius of gyration, enabling realistic behavioral modeling. Second, a data generation engine constructs geographically grounded simulations using OpenStreetMap data to produce diverse mobility logs. Third, a data processing suite transforms raw simulation logs into structured formats suitable for downstream applications, including model training and benchmarking.

Merge trees are a valuable tool in the scientific visualization of scalar fields; however, current methods for merge tree comparisons are computationally expensive, primarily due to the exhaustive matching between tree nodes. To address this challenge, we introduce the Merge Tree Neural Network (MTNN), a learned neural network model designed for merge tree comparison. The MTNN enables rapid and high-quality similarity computation. We first demonstrate how to train graph neural networks, which emerged as effective encoders for graphs, in order to produce embeddings of merge trees in vector spaces for efficient similarity comparison. Next, we formulate the novel MTNN model that further improves the similarity comparisons by integrating the tree and node embeddings with a new topological attention mechanism. We demonstrate the effectiveness of our model on real-world data in different domains and examine our model's generalizability across various datasets. Our experimental analysis demonstrates our approach's superiority in accuracy and efficiency. In particular, we speed up the prior state-of-the-art by more than 100× on the benchmark datasets while maintaining an error rate below 0.1%.

We demonstrate the Patterns of Life Simulation to create realistic simulations of human mobility in a city. This simulation has recently been used to generate massive amounts of trajectory and check-in data. Our demonstration focuses on using the simulation twofold: (1) using the graphical user interface (GUI), and (2) running the simulation headless by disabling the GUI for faster data generation. We further demonstrate how the Patterns of Life simulation can be used to simulate any region on Earth by using publicly available data from OpenStreetMap. Finally, we also demonstrate recent improvements to the scalability of the simulation allows simulating up to 100,000 individual agents for years of simulation time. During our demonstration, as well as offline using our guides on GitHub, participants will learn: (1) The theories of human behavior driving the Patters of Life simulation, (2) how to simulate to generate massive amounts of synthetic yet realistic trajectory data, (3) running the simulation for a region of interest chosen by participants using OSM data, (4) learn the scalability of the simulation and understand the properties of generated data, and (5) manage thousands of parallel simulation instances running concurrently.

Individual human location trajectory and check-in data have been the driving force for human mobility research in recent years. However, existing human mobility datasets are very limited in size and representativeness. For example, one of the largest and most commonly used datasets of individual human location trajectories, GeoLife, captures fewer than two hundred individuals. To help fill this gap, this Data and Resources paper leverages an existing data generator based on fine-grained simulation of individual human patterns of life to produce large-scale trajectory, check-in, and social network data. In this simulation, individual human agents commute between their home and work locations, visit restaurants to eat, and visit recreational sites to meet friends. We provide large datasets of months of simulated trajectories for two example regions in the United States: San Francisco and New Orleans. In addition to making the datasets available, we also provide instructions on how the simulation can be used to re-generate data, thus allowing researchers to generate the data locally without downloading prohibitively large files.

The free space diagram is a popular tool to compute the well-known Fréchet distance. As the Fréchet distance is used in many different fields, many variants have been established to cover the specific needs of these applications. Often the question arises whether a certain pattern in the free space diagram is realizable, i.e., whether there exists a pair of polygonal chains whose free space diagram corresponds to it. The answer to this question may help in deciding the computational complexity of these distance measures, as well as allowing to design more efficient algorithms for restricted input classes that avoid certain free space patterns. Therefore we study the inverse problem: Given a potential free space diagram, do there exist curves that generate this diagram? Our problem of interest is closely tied to the classic Distance Geometry problem. We settle the complexity of Distance Geometry in ℝ^{>2}, showing ∃ℝ-hardness. We use this to show that for curves in ℝ^{≥2} the realizability problem is ∃ℝ-complete, both for continuous and for discrete Fréchet distance. We prove that the continuous case in ℝ¹ is only weakly NP-hard, and we provide a pseudo-polynomial time algorithm and show that it is fixed-parameter tractable. Interestingly, for the discrete case in ℝ¹ we show that the problem becomes solvable in polynomial time.

Persistence diagrams have been widely used to quantify the underlying features of filtered topological spaces in data visualization. In many applications, computing distances between diagrams is essential; however, computing these distances has been challenging due to the computational cost. In this paper, we propose a persistence diagram hashing framework that learns a binary code representation of persistence diagrams, which allows for fast computation of distances. This framework is built upon a generative adversarial network (GAN) with a diagram distance loss function to steer the learning process. Instead of using standard representations, we hash diagrams into binary codes, which have natural advantages in large-scale tasks. The training of this model is domain-oblivious in that it can be computed purely from synthetic, randomly created diagrams. As a consequence, our proposed method is directly applicable to various datasets without the need for retraining the model. These binary codes, when compared using fast Hamming distance, better maintain topological similarity properties between datasets than other vectorized representations. To evaluate this method, we apply our framework to the problem of diagram clustering and we compare the quality and performance of our approach to the state-of-the-art. In addition, we show the scalability of our approach on a dataset with 10k persistence diagrams, which is not possible with current techniques. Moreover, our experimental results demonstrate that our method is significantly faster with the potential of less memory usage, while retaining comparable or better quality comparisons.

We introduce new distance measures for comparing straight-line embedded graphs based on the Fréchet distance and the weak Fréchet distance. These graph distances are defined using continuous mappings and thus take the combinatorial structure as well as the geometric embeddings of the graphs into account. We present a general algorithmic approach for computing these graph distances. Although we show that deciding the distances is NP-hard for general embedded graphs, we prove that our approach yields polynomial time algorithms if the graphs are trees, and for the distance based on the weak Fréchet distance if the graphs are planar embedded and if the embedding meets a certain geometric restriction. Moreover, we prove that deciding the distances based on the Fréchet distance remains NP-hard for planar embedded graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case.

We study the interplay between the recently-defined concept of minimum homotopy area and the classical topic of self-overlapping curves. The latter are plane curves that are the image of the boundary of an immersed disk. Our first contribution is to prove new sufficient combinatorial conditions for a curve to be self-overlapping. We show that a curve γ with Whitney index 1 and without any self-overlapping subcurves is self-overlapping. As a corollary, we obtain sufficient conditions for self-overlapping ness solely in terms of the Whitney index of the curve and its subcurves. These results follow from our second contribution, which shows that any plane curve γ, modulo a basepoint condition, is transformed into an interior boundary by wrapping around γ with Jordan curves. In fact, we show that n+1 wraps suffice, where γ has n vertices. Our third contribution is to prove the equivalence of various definitions of self-overlapping curves and interior boundaries, often implicit in the literature. We also introduce and characterize zero-obstinance curves, a further generalization of interior boundaries defined by optimality in minimum homotopy area.

Location-based social networks (LBSNs) have been studied extensively in recent years. However, utilizing real-world LBSN data sets yields several weaknesses: sparse and small data sets, privacy concerns, and a lack of authoritative ground-truth. To overcome these weaknesses, we leverage a large-scale LBSN simulation to create a framework to simulate human behavior and to create synthetic but realistic LBSN data based on human patterns of life. Such data not only captures the location of users over time but also their interactions via social networks. Patterns of life are simulated by giving agents (i.e., people) an array of “needs” that they aim to satisfy, e.g., agents go home when they are tired, to restaurants when they are hungry, to work to cover their financial needs, and to recreational sites to meet friends and satisfy their social needs. While existing real-world LBSN data sets are trivially small, the proposed framework provides a source for massive LBSN benchmark data that closely mimics the real-world. As such, it allows us to capture 100% of the (simulated) population without any data uncertainty, privacy-related concerns, or incompleteness. It allows researchers to see the (simulated) world through the lens of an omniscient entity having perfect data. Our framework is made available to the community. In addition, we provide a series of simulated benchmark LBSN data sets using different synthetic towns and real-world urban environments obtained from OpenStreetMap. The simulation software and data sets, which comprise gigabytes of spatio-temporal and temporal social network data, are made available to the research community.

Due to its many applications, curve simplification is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve P' with a smaller number of vertices such that P' is sufficiently similar to P. Quality guarantees of a simplification are usually given in a local sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work we aim to provide a systematic overview of curve simplification problems under global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the Fréchet distance. And we study different restrictions on the choice of vertices for P'. We provide polynomial-time algorithms for some variants of the global curve simplification problem, and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.

Data generators have been heavily used in creating massive trajectory datasets to address common challenges of real-world datasets, including privacy, cost of data collection, and data quality. However, such generators often overlook social and physiological characteristics of individuals and as such their results are often limited to simple movement patterns. To address these shortcomings, we propose an agent-based simulation framework that facilitates the development of behavioral models in which agents correspond to individuals that act based on personal preferences, goals, and needs within a realistic geographical environment. Researchers can use a drag-and-drop interface to design and control their own world including the geospatial and social (i.e. geo-social) properties. The framework is capable of generating and streaming very large data that captures the basic patterns of life in urban areas. Streaming data from the simulation can be accessed in real time through a dedicated API.

Location-based social networks (LBSNs) have been studied extensively in recent years. However, utilizing real-world LBSN datasets in such studies has severe weaknesses: sparse and small datasets, privacy concerns, and a lack of authoritative ground-truth. Our vision is to create a large scale geo-simulation framework to simulate human behavior and to create synthetic but realistic LBSN data that captures the location of users over time as well as social interactions of users in a social network. While existing LBSN datasets are trivially small, such a framework would provide the first source of massive LBSN benchmark data which would closely mimic the real world, containing high-fidelity information of location, and social connections of millions of simulated agents over several years of simulated time. Therefore, it would serve the research community by revitalizing and reshaping research on LBSNs by allowing researchers to see the (simulated) world through the lens of an omniscient entity having perfect data. These evaluations will guide future research enabling us to develop solutions to improve LBSN applications such as user-location recommendation, friend recommendation, location prediction, and location privacy.

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.

Due to the ubiquitous use of various positioning technologies in smart phones and other devices, geospatial tracking data has become a routine data source. One of its uses that has gained recent popularity is the construction of street maps from vehicular tracking data. Due to the inherent noise in the data, many map construction algorithms are based on thresholding a density function. While kernel density estimation provides a firm theoretical foundation for computing the density from the measurements, the thresholds are generally picked in a heuristic, and often brute-force way, which results in slow algorithms with no guarantees on the map construction quality.

We define a topology-based distance metric between road networks embedded in the plane. This distance measure is based on local persistent homology, and employs a local distance signature that enables identification and visualization of local differences between the road networks. This paper is motivated by the need to recognize changes in road networks over time and to assess the quality of different map construction algorithms. One particular challenge is evaluating the results when no ground truth is known. However, we demonstrate that we can overcome this hurdle by using a statistical technique known as the bootstrap.

We extend recent results using curve simplification for approximating the Fréchet distance of realistic curves in near linear time to map matching: the problem of matching a curve in an embedded graph.We show that the theoretical bounds on the running time of the previous result still hold if only one of the curves is simplified during the course of the approximation algorithm.This enables our extension to the case of map matching under the assumption that the graph is φ-low density for a constant φ.We present experimental evidence for this assumption and implement the extended approximate matching algorithm.We show that it performs well on real world data, such as GPS traces and road networks of urban areas.In particular, it is able to perform matching tasks that took several hours with the exact matching algorithm in under a second.

We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between polygonal curves. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and show similar results for other input models, such as low density.

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.

We present an alternative to parametric search that applies to both the nongeodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search. We introduce the first algorithm to compute the geodesic Fréchet distance between two polygonal curves A and B inside a simple bounding polygon P . The geodesic Fréchet decision problem is solved almost as fast as its nongeodesic sibling in O ( N 2 log k ) time and O ( k + N ) space after O(k) preprocessing, where N is the larger of the complexities of A and B and k is the complexity of P . The geodesic Fréchet optimization problem is solved by a randomized approach in O ( k + N 2 log kN log N ) expected time and O ( k + N 2 ) space. This runtime is only a logarithmic factor larger than the standard nongeodesic Fréchet algorithm [Alt and Godau 1995]. Results are also presented for the geodesic Fréchet distance in a polygonal domain with obstacles and the geodesic Hausdorff distance for sets of points or sets of line segments inside a simple polygon P .

The essential elements of any navigation system are a shortest-path algorithm and accurate map data. The contribution of this work is two-fold. First, the HBA* algorithm, an efficient shortest-path algorithm is presented that mimics human driving behavior by exploiting road network hierarchies. Second, in a thorough performance study dynamic travel times are introduced to replace the unreliable static speed types currently used in connection with road network datasets.

We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fr{'\e}chet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search. We present the first algorithm for the geodesic Fr{'\e}chet distance between two polygonal curves $A$ and $B$ inside a simple bounding polygon $P$. The geodesic Fr{'\e}chet decision problem is solved almost as fast as its non-geodesic sibling and requires $O(N^{2log k)$ time and $O(k+N)$ space after $O(k)$ preprocessing, where $N$ is the larger of the complexities of $A$ and $B$ and $k$ is the complexity of $P$. The geodesic Fr{'\e}chet optimization problem is solved by a randomized approach in $O(k+N^{2log kNlog N)$ expected time and $O(k+N^{2)$ space. This runtime is only a logarithmic factor larger than the standard non-geodesic Fr{'\e}chet algorithm (Alt and Godau 1995). Results are also presented for the geodesic Fr{'\e}chet distance in a polygonal domain with obstacles and the geodesic Hausdorff distance for sets of points or sets of line segments inside a simple polygon $P$.

We present the first polynomial-time algorithm for computing the Fréchet for a non-trivial class of surfaces: simple polygons. For this, we show that it suffices to consider homeomorphisms that map an arbitrary triangulation of one polygon to the other polygon such that diagonals of the triangulation are mapped to shortest paths in the other polygon.

With vehicle tracking data becoming an important sensor data resource for a range of applications related to traffic assessment and prediction, fast and accurate mapmatching algorithms become a necessary means to ultimately utilize this data. This work proposes a fast mapmatching algorithm which exploits tracking data error estimates in a provably correct way and offers a quality guarantee for the computed result trajectory. A new model for the map-matching task is introduced which takes tracking error estimates into account. The proposed Adaptive Clipping algorithm (i) provably solves this map-matching task and (ii) utilizes the weak Fr´echet distance to measure similarity between curves. The algorithm uses the error estimates in the trajectory data to reduce the search space (error-aware pruning), while offering the quality guarantee of finding a curve which minimizes the weak Fr´echet distance to the vehicle trajectory among all possible curves in the road network. Moreover, this work introduces an outputsensitive variant of an existing weak Fr´echet map-matching algorithm, which is also employed in the Adaptive Clipping algorithm. Output-sensitiveness paired with error-aware pruning makes Adaptive Clipping the first map-matching algorithm that provably solves a well-defined map-matching task. An experimental evaluation establishes further that Adaptive Clipping is also in a practical setting a fast algorithm that at the same time produces high-quality matching results.

Given a polygonal curve and a geometric graph, we describe an efficient algorithm to find a path in the graph which is most similar to the curve, using the well-known Fréchet distance for curves.

No abstract available.

In proteomics 2-dimensional gel electrophoresis (2-DE) is a separation technique for proteins. The resulting protein spots can be identified by either using picking robots and subsequent mass spectrometry or by visual cross inspection of a new gel image with an already analyzed master gel. Difficulties especially arise from inherent noise and irregular geometric distortions in 2-DE images. Aiming at the automated analysis of large series of 2-DE images, or at the even more difficult interlaboratory gel comparisons, the bottleneck is to solve the two most basic algorithmic problems with high quality: Identifying protein spots and computing a matching between two images. For the development of the analysis software CAROL at Freie Universität Berlin we have reconsidered these two problems and obtained new solutions which rely on methods from computational geometry. Their novelties are: 1. Spot detection is also possible for complex regions formed by several “merged” (usually saturated) spots; 2. User-defined landmarks are not necessary for the matching. Furthermore, images for comparison are allowed to represent different parts of the entire protein pattern, which only partially “overlap”. The implementation is done in a client server architecture to allow queries via the Internet. We also discuss and point at related theoretical questions in computational geometry.

A new algorithmic approach to comparing 2D patterns of protein spots obtained by the 2D gel electrophoresis technique is presented. Both the matching of a local pattern vs. a full 2D gel image and the global matching between full images are discussed. The local matching algorithm relies on a data structure derived from the incremental Delaunay triangulation of a point set and a 2--step hashing technique. The approach for the global matching uses local matching for landmark settings, which in previous algorithmic solutions has been done interactively by the user. *Part of a joint research project with Deutsches Herzzentrum Berlin, supported by Deutsche Forschungsgemeinschaft, grant FL 165/4--1. **Institut fur Informatik, Freie Universitat Berlin, Takustr. 9. D-14195 Berlin E-mail: [email protected] 2 1 Introduction 1.1 Point Pattern Matching The matching problem for geometric point patterns has been subject of intensive research in the last decade. Given a point pattern P and an...