Jörg-Rüdiger Sack

TCS Journal 2019 Journal Article

Weighted minimum backward Fréchet distance

• Amin Gheibi
• Anil Maheshwari
• Jörg-Rüdiger Sack

The minimum backward Fréchet distance (MBFD) problem is a natural optimization problem for the weak Fréchet distance, a variant of the well-known Fréchet distance. In this problem, a threshold ε and two polygonal curves, T 1 and T 2, are given. The objective is to find a pair of walks on T 1 and T 2, which minimizes the union of the portions of backward movements (backtracking) while maintaining, at any time, a distance between the moving entities of at most ε. In this paper, we generalize this model to capture scenarios when the cost of backtracking on the input polygonal curves is not homogeneous. More specifically, each edge of T 1 and T 2 has an associated non-negative weight. The cost of backtracking on an edge is the Euclidean length of backward movement on that edge multiplied by the corresponding weight. The objective is to find a pair of walks that minimizes the sum of the costs on the edges of the curves, while guaranteeing that the weak traversal of the curves maintains a weak Fréchet distance of at most ε. We propose two exact algorithms, a simple algorithm with O ( n 4 ) time and space complexities and an improved algorithm whose time and space complexities are O ( n 2 log 3 / 2 ⁡ n ), where n is the maximum number of the edges of T 1 and T 2. A solution to weighted MBFD also implies a solution to the more general optimization problem in which both backward and forward movements have associated costs.

MFCS Conference 2006 Conference Paper

Approximate Shortest Path Queries on Weighted Polyhedral Surfaces

• Lyudmil Aleksandrov
• Hristo N. Djidjev
• Hua Guo
• Anil Maheshwari
• Doron Nussbaum
• Jörg-Rüdiger Sack

Abstract We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface P consisting of n triangular faces. We present query algorithms that compute approximate distances and/or approximate (weighted) shortest paths. Our algorithm takes as input an approximation parameter ε ∈(0, 1) and a query time parameter \(\mathfrak{q}\) and builds a data structure which is then used for answering ε -approximate distance queries in \(O(\mathfrak{q})\) time. This algorithm is source point independent and improves significantly on the best previous solution. For the case where one of the query points is fixed we build a data structure that can answer ε -approximate distance queries to any query point in P in \(O(\log\frac{1}{\varepsilon})\) time. This is an improvement upon the previously known solution for the Euclidean fixed source query problem. Our algorithm also generalizes the setting from previously studied unweighted polyhedral to weighted polyhedral surfaces of arbitrary genus. Our solutions are based on a novel graph separator algorithm introduced here which extends and generalizes previously known separator algorithms.

STOC Conference 2000 Conference Paper

Approximation algorithms for geometric shortest path problems

• Lyudmil Aleksandrov
• Anil Maheshwari
• Jörg-Rüdiger Sack

TCS Journal 1997 Journal Article

Planar stage graphs: Characterizations and applications

• Frank Bauernöppel
• Evangelos Kranakis
• Danny Krizanc
• Anil Maheshwari
• Jörg-Rüdiger Sack
• Jorge Urrutia

We consider combinatorial and algorithmic aspects of the well-known paradigm “killing two birds with one stone”. We define a stage graph as follows: vertices are points from a planar point set, and {u, v} is an edge if and only if the (infinite, straight) line segment joining u to v intersects a given line segment, called a stage. We show that a graph is a stage graph if and only if it is a permutation graph. The characterization results in a compact linear space representation of stage graphs. This has been exploited for designing improved algorithms for maximum matching in permutation graphs, two processor task scheduling for dependency graphs known to be permutation graphs, and dominance-related problems for planar point sets. We show that a maximum matching in permutation graphs can be computed in Ω(n log2 n) time, where n is the number of vertices. We provide simple optimal sequential and parallel algorithms for several dominance related problems for planar point sets.

I&C Journal 1990 Journal Article

A characterization of heaps and its applications

• Jörg-Rüdiger Sack
• Thomas Strothotte

In this paper we present a new view of a classical data structure, the heap. We view a heap on n elements as an ordered collection of ⌜log2(n + 1)⌝ substructures of sizes 2 i with i in {0, …, ⌈log2(n)⌉}. We use the new view in the design of an algorithm for splitting a heap on n elements into two heaps on k and n − k elements, respectively. The algorithm requires O(log2(n)) comparisons, improving the previous bound of O(k) comparisons for all but small values of k, i. e. , for k log2(n). We also present a new and conceptually simple algorithm for merging heaps of sizes n and k into one heap of size n + k in O(log(n) ∗ log(k)) comparisons.