Journal Publications

 

Rene Beier, Stefan Funke, Domagoj Matijevic, Peter Sanders
Energy-Efficient Paths In Radio Networks
to appear in Algorithmica, 2010.
(part of the results appeared in ESA 2003)

ABSTRACT: We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ω(p, q) = |pq|^δ +C_p, for some constant δ > 1 and nonnegative offset costs C_p. Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops. We present an exact algorithm for the important case when δ = 2, which requires O(kn log n) time per query pair (p, q). For the case of an unrestricted number of hops we describe a family of algorithms with query time O(n^(1+alpha)), where alpha > 0 can be chosen arbitrarily. If we relax the exactness requirement, we can find an approximate (1+eps) solution in constant time by querying a data structure which has linear size and which can be build in O(n log n) time. One tool we employ might be of independent interest: For any pair of points (p, q) we can report in constant time the cluster pair (A,B) representing (p, q) in a well-separated pair decomposition of P.

PRG logo
Khaled Elbassioni, Erik Krohn, Domagoj Matijević, Julian Mestre, Domagoj Ševerdija
Improved Approximations for Guarding 1.5-Dimensional Terrains
to appear in Algorithmica, 2009.
(extended abstract appeared in STACS 2009)

ABSTRACT: We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.

PRG logo
Domagoj Matijević, Ralf Osbild
Finding the Theta-Guarded Region
to appear in Computational Geometry: Theory and Applications (CGTA), 2009.

ABSTRACT:We are given a finite set of points (\emph{guards}) in the plane. A \Theta-cone is a cone with apex angle \Theta. We call a \Theta-cone empty, if it does not contain any guards in its interior. A point p is called \Theta-guarded, if every \Theta-cone with apex located at p is non-empty. The set of all \Theta-guarded points is called the \Theta-guarded region, or the $\Theta$-region for short. The rationale behind this model is that a point is well-guarded only if it is guarded from all sides. In this paper we show the bound for the complexity of the \Theta-region as well as present the algorithms for computing it.

PRG logo
Jens Maue, Peter Sanders, Domagoj Matijević
Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
ACM Journal of Experimental Algorithmics (ACM JEA), 14/3, 2009
(extended abstract appeared in WEA 2006)

ABSTRACT: We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely exible tradeo between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong sense of direction". We evaluate our approach experimentally using large, real-world road networks.

 PRG logo
Soeren Laue, Domagoj Matijević
Approximating k-hop Minimum Spanning Trees in Euclidean metrics
Information Processing Letters (IPL) , 107/3-4:96-101, 2008.
(extended abstract appeared in CCCG 2007)

ABSTRACT:In the minimum-cost k-hop spanning tree (k-hop MST) problem, we are given a set of n points in a metric space, a positive small integer k and a root point r. We are interested in computing a rooted spanning tree of minimum cost such that the longest root-leaf path in the tree has at most k edges. We present a polynomial-time approximation scheme for the plane. Our algorithm is based on Arora's et al. technique for the Euclidean k-median problem.

 PRG logo
Stefan Funke, Domagoj Matijević, Peter Sanders
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
Journal of Computing and Information Technology (CIT), 16/2:119-130, 2008
(extended abstract appeared in A_SWAN 2004)

ABSTRACT: We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the position of radio stations in such a way that approximately energy optimal paths can be retrieved in constant time, i.e., independent of the network size. We put particular emphasis on actual implementations which demonstrate that large constant factors hidden in the theoretical analysis are not a big problem in practice.

 PRG logo
Energy-Aware Stage Illumination
Friedrich Eisenbrand, Stefan Funke, Andreas Karrenbauer, Domagoj Matijević
International Journal of Computational Geometry and Applications (IJCGA), 18/1-2:107-129, 2008
(extended abstract appeared in SCG 2005, implementation published in Wolfram Demonstrations Project)

ABSTRACT: Consider the following illumination problem: given a stage represented by a line segment and a set of lightsources represented by a set of points in the plane, assign powers to the lightsources such that every point on the stage receives a sufficient amount, let's say one unit, of light while minimizing the overall power consumption. By assuming that the amount of light arriving from a fixed lightsource decreases rapidly with the distance from the lightsource, this becomes an interesting optimization problem. We propose to reconsider the classical illumination problems as known from computational geometry literature under this light attenuation model. This paper examines the simple problem introduced above and presents different solutions, based on convex optimization, discretization and linear programming, as well as a purely combinatorial approximation algorithm.

 PRG logo

 

Refereed Proceedings