Approximate Shortest Path Queries on Weighted Polyhedral Surfaces ⋆ (2009)
Lyudmil Aleks, 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...
08451 Summary Report -- Representation, Analysis and Visualization of Moving Objects (2009)
Bitterlich, Wolfgang, Sack, Jörg-Rüdiger, Sester, Monika, Weibel, Robert
This document contains a short report summarizing the background, the program, and the outcomes of Dagstuhl Seminar 08451 on "Representation, Analysis and Visualization of Moving Objects".
08451 Abstracts Collection -- Representation, Analysis and Visualization of Moving Objects (2009)
Bitterlich, Wolfgang, Sack, Jörg-Rüdiger, Sester, Monika, Weibel, Robert
From 02.11. to 07.11.2008, the Dagstuhl Seminar 08451 ``Representation, Analysis and Visualization of Moving Objects '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the...
On the longest increasing subsequence of a circular list (2008)
Jörg-rüdiger Sack, Nicola Santoro
The longest increasing circular subsequence (LICS) of a list is considered. A Monte-Carlo algorithm to compute it is given which has worst case execution time O(n 3/2 log n) and storage requirement...
On the longest increasing subsequence of a circular list (2008)
Jörg-rüdiger Sack, Nicola Santoro
The longest increasing circular subsequence (LICS) of a list is considered. A Monte-Carlo algorithm to compute it is given which has worst case execution time O(n 3/2 log n) and storage requirement...
Current & Future Issues of High-End Computing, (2008)
D. Nussbaum, H. Ye, G. R. Joubert, W. E. Nagel, F. J. Peters, ...
Permission to make digital or hard copies of portions of this work for personal or classroom use is granted provided that the copies are not made or distributed for profit or commercial advantage and...
Approximating Shortest Paths on Weighted Polyhedral Surfaces (2007)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Shortest path problems are among the... In this paper we propose several simple and practical algorithms (schemes) to compute an approximated weighted shortest path Π'(s, t) points s and...
A Framework for Multiresolution Modelling (2007)
Anil Maheshwari, Pat Morin, Jörg-Rüdiger Sack
Introduction The subject of multiresolution surface modelling has received considerable attention from a number of fields, including computational geometry, geographic information systems, and...
Inverse Distributions and Independent Gamma-Distributed Products of Random Variables (2007)
Luc Devroye, Peter Epstein, Jörg-rüdiger Sack, Luc Devroye, Peter Epstein, Jörg-rüdiger Sack, ...
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use...
Approximate shortest path queries on weighted polyhedral surfaces (2006)
Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-rüdiger Sack
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...
06101 Report -- Spatial Data: mining, processing and communicating (2006)
Sack, Jörg-Rüdiger, Sester, Monika, Worboys, Michael, Van Oosterom, Peter
This workshop has been organized as a successor to four preceding ones. The major goal has been to bring together experts from digital cartography, spatial modelling, computational geometry and...
06101 Abstracts Collection -- Spatial Data:mining, processing and communicating (2006)
Sack, Jörg-Rüdiger, Sester, Monika, Worboys, Michael, Van Oosterom, Peter
From 05.03.06 to 10.03.06, the Dagstuhl Seminar 06101 ``Spatial Data: mining, processing and communicating'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl....
The complexity of implicit and space-efficient priority queues (2005)
Mortensen, Christian W, Pettie, Seth, Dehne, Frank, López-Ortiz, Alejandro, Sack, Jörg-Rüdiger
Parallel Implementation of Geometric Shortest Path Algorithms (2003)
Mark Lanthier, Doron Nussbaum, Jörg-Rüdiger Sack
In application areas such as GIS, the Euclidean metric is often less meaningfully applied to determine a shortest path than metrics which capture, through weights, the varying nature of the terrain...
Progressive TINs: Algorithms and Applications (1997)
Anil Maheshwari, Pat Morin, Jörg-Rüdiger Sack
Transmission of geographic data over the Internet, rendering at different resolutions/levels of detail, or processing at unnecessarily fine detail pose interesting challenges and opportunities. In...
Early Experiences in Implementing the Buffer Tree (1997)
David Hutchinson, Anil Maheshwari, Jörg-Rüdiger Sack, Radu Velicescu
Computer processing speeds are increasing rapidly due to the evolution of faster chips, parallel processing of data, and more efficient software. Users today have access to an unprecedented amount of...
Approximating Weighted Shortest Paths on Polyhedral Surfaces (1997)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Consider a simple polyhedron P, possibly non-convex, composed of n triangular regions (faces), in which each region has an associated positive weight. The cost of travel through each region is the...
Approximating Weighted Shortest Paths on Polyhedral Surfaces (1997)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Introduction Shortest path problems are among the fundamental problems studied in computational geometry. In this video, we consider the problem of computing a shortest cost path between two points s...
Approximating Weighted Shortest Paths on Polyhedral Surfaces (1996)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
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...
Stage-Graph Representations (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Marc Noy, Jörg-Rüdiger Sack, Jorge Urrutia
We consider graph applications of the well-known paradigm "killing two birds with one stone". In the plane, this gives rise to a stage graph as follows: vertices are the points, and fu; vg...
Ray Shooting from Convex Ranges (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
We consider geometric and graph-theoretic aspects of the well-known paradigm "killing two birds with one stone". Consider that we have a set X of n-points in space and a compact plane...
Planar Stage Graphs: Characterizations And Applications (1995)
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 the points from a planar...
An Improved Maximum Matching Algorithm in a Permutation Graph (1995)
Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
Introduction We present an O(n log 2 n) time algorithm for computing a maximum matching in a permutation graph on n-vertices. Our results are based on the algorithm of [12] for a two processor...
Experiences with the implementation of geometric algorithms (1995)
Mehlhorn, Kurt, Akl, Selim G., Dehne, Frank, Sack, Jörg-Rüdiger, Santoro, Nicola
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette, Sack, Jörg-Rüdiger, Santoro, Nicola, ...
Optimal Parallel Algorithms for Rectilinear Link Distance Problems (1992)
Andrzej Lingas, Anil Maheshwari, Jörg-Rüdiger Sack
We provide optimal parallel solutions to several link distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the...