A pseudo-polynomial time $(1 + \varepsilon)$-approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves $T_1$ and $T_2$. In particular, the running time is upper-bounded by $\mathcal{O}( ζ^{4}n^4/\varepsilon^{2})$ where $n$ is the complexity of $T_1$ and $T_2$ and $ζ$ is the maximal ratio of the lengths of any pair of segments from $T_1$ and $T_2$. The Fréchet distance captures the minimal cost of a continuous deformation of $T_1$ into $T_2$ and vice versa and defines the cost of a deformation as the maximal distance between two points that are related. The integral Fréchet distance defines the cost of a deformation as the integral of the distances between points that are related. The average Fréchet distance is defined as the integral Fréchet distance divided by the lengths of $T_1$ and $T_2$. Furthermore, we give relations between weighted shortest paths inside a single parameter cell $C$ and the monotone free space axis of $C$. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.

Hospitals and health care organizations collect large amounts of detailed health care data that is in high demand by researchers. Thus, the possessors of such data are in need of methods that allow for this data to be released without compromising the confidentiality of the individuals to whom it pertains. As the geographic aspect of this data is becoming increasingly relevant for research being conducted, it is important for an anonymization process to pay due attention to the geographic attributes of such data. In this paper, a novel system for health care data anonymization is presented. At the core of the system is the aggregation of an initial regionalization guided by the use of a Voronoi diagram. We conduct a comparison with another location-based system of anonymization, GeoLeader. We show that our system is capable of producing results of a comparable quality with a much faster running time.

We propose a new measure to capture similarity between polygonal curves, called the minimum backward Fréchet distance. It is a natural optimization on the weak Fréchet distance, a variant of the well-known Fréchet distance. More specifically, for a given threshold ε, we are searching for a pair of walks for two entities on the two input curves, T1 and T2, such that the union of the portions of backward movements is minimized and the distance between the two entities, at any time during the walk, is less than or equal to ε. Our algorithm detects if no such pair of walks exists. This natural optimization problem appears in many applications in Geographical Information Systems, mobile networks and robotics. We provide an exact algorithm with time complexity of O(n2 log n) and space complexity of O(n2), where n is the maximum number of segments in the input polygonal curves.

The capability to query the topology of spatial regions is fundamental to today's centralized spatial computing systems, like spatial databases and GIS. By contrast, this paper explores decentralized algorithms for computing the topology of spatial regions in wireless sensor networks. The approach generates global topological information about regions, using only the local knowledge of nodes and their immediate network neighbors aggregated up through spatial boundary structures. Using three basic boundary structures (boundary nodes, boundary cycles, and boundary orientation), a family of decentralized algorithms is defined that can respond efficiently to snapshot queries about the topology of spatial regions, including containment and adjacency queries. The communication complexity of the algorithm is O(n) for realistic inputs. Empirical investigation of the performance of the approach, using simulation, also confirms the efficiency, scalability, and robustness of this approach.

We are studying the problem of determining suitable meeting times and locations for a group of participants wishing to schedule a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant must be able to reach the new meeting location, attend for the entire duration, and reach the next meeting location on time. In particular, we give a solution to the problem instance where each participant has two scheduled meetings separated by a free time interval. For a geometric model, where n participants can travel along straight paths in the Euclidean plane, we present an O(n log n) algorithm to determine the longest meeting duration and a location suitable to all participants. In a graph-based model, transportation is provided by a geometric network over m nodes and e edges in the plane. Participants can have individual weights. Moreover, there can be k groups of participants, such that only one member of each group must attend the meeting. In this model, a location for a meeting of longest possible duration can be determined in time O(enalpha(k) log k + n log n + mn log m), where alpha(k) denotes the extremely slowly growing inverse Ackermann function

In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an associated positive weight. The cost of travel through a face is the Euclidean distance traveled, multiplied by the face's weight. For a given parameter ε, 0 <ε < 1, the cost of the computed paths is at most 1 + ε times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C(P) n /√ε log n /ε log 1/ε) time, where C(P) captures geometric parameters and the weights of the faces of P .

We consider the classical geometric problem of determining a shortest path through a weighted domain.We present approximation algorithms that compute e-short paths, i.e., paths whose costs are within a factor of 1 + e of the shortest path costs, for an arbitrary constant e > O, for the following geometric configurations: O n 1 1 runs in (~ log ; (~ +log n)) time.The run time improves to O(;~-log ~logn)) when all weights are equal.This can be used to solve the shortest path problem amidst obstacles in 3-dimensional Euclidean space (ESP-3D).

Consider a simple polyhedron P, possibly non-convex, composed of n triangular regions (faces), each assigned a positive weight indicating the cost of travel in that region. We present and experimentally study several algorithms to compute an approximate weighted geodesic shortest path, ß 0 (s; t), between two points s and t on the surface of P. Our algorithms are simple, practical, less prone to numerical problems, adaptable to a wide spectrum of weight functions, and use only elementary data structures. An additional feature of our algorithms is that execution time and space utilization can be traded off for accuracy; likewise, a sequence of approximate shortest paths for a given pair of points can be computed with increasing accuracy (and execution time) if desired. Dynamic changes to the polyhedron (removal, insertions of vertices or faces) are easily handled. The key step in these algorithms is the construction of a graph by introducing Steiner points on the edges of the given p...

No abstract available.

We are constructing a workbench for computational geometry. This is intended to provide a framework for the implementation, testing, demonstration and application of algorithms in computational geometry. The workbench is being written in Smalltalk/V using an Apple Macintosh II.

Notation and a theorem are presented which, using a result of B. Chazelle and L.J. Guibas (1985), enable the authors to design an O(n log n) algorithm for reporting all visibility edges of a given n-vertex polygon. Improving on this bound to O(n) is presently focused upon. This problem is solved for polygons with at least one given visibility edge. It is assumed that both endpoints of this edge are convex vertices. Subsequently, it is shown how to drop this restriction. The general case of detecting weak edge visibility of an arbitrary simple polygon is dealt with.>

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time Ο (n2), where n is the number of sides of P. We also give an Ο(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.