20 citations · 64 across the 26 of their papers we have counts for
26 papers · 1 filter
Theoretical analysis of beaconless geocast protocols in 1D
Joachim Gudmundsson, Irina Kostitsyna, Maarten Löffler +3
Beaconless geocast protocols are routing protocols used to send messages in mobile ad-hoc wireless networks, in which the only information available to each node is its own locatio…
Shortest Paths in Portalgons
Maarten Löffler, Tim Ophelders, Frank Staals +1
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragmen…
Efficient Fréchet distance queries for segments
Maike Buchin, Ivor van der Hoog, Tim Ophelders +3
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve , such that for any query segment one can efficiently comp…
On approximating shortest paths in weighted triangular tessellations
Prosenjit Bose, Guillermo Esteban, David Orden +1
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessel…
Continuous mean distance of a weighted graph
Delia Garijo, Alberto Márquez, Rodrigo I. Silveira
We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances…
Terrain prickliness: theoretical grounds for high complexity viewsheds
Ankush Acharyya, Maarten Löffler, Gert G. T. Meijer +3
An important task in terrain analysis is computing \emph{viewsheds}. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewp…
Affine invariant triangulations
Prosenjit Bose, Pilar Cano, Rodrigo I. Silveira
We study affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set for any (unknown) affine transformation of . Our wor…
A new lower bound on the maximum number of plane graphs using production matrices
Clemens Huemer, Alexander Pilz, Rodrigo I. Silveira
We use the concept of production matrices to show that there exist sets of points in the plane that admit crossing-free geometric graphs. This improves the previou…
Matching points with disks with a common intersection
Clemens Huemer, Pablo Pérez-Lantero, Carlos Seara +1
We consider matchings with diametral disks between two sets of points R and B. More precisely, for each pair of matched points p in R and q in B, we consider the disk through p and…
Computing optimal shortcuts for networks
Delia Garijo, Alberto Márquez, Natalia Rodríguez +1
We study augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the largest distance between any two points along the edges of the resulting network. P…
Balanced partitions of 3-colored geometric sets in the plane
Sergey Bereg, Matias Korman, Rodrigo I. Silveira +6
Let be a finite set of geometric objects partitioned into classes or \emph{colors}. A subset is said to be \emph{balanced} if contains the same amount of e…
Non-crossing paths with geographic constraints
Rodrigo I. Silveira, Bettina Speckmann, Kevin Verbeek
A geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geog…
Stabbing segments with rectilinear objects
Mercè Claverol, Delia Garijo, Matias Korman +2
Given a set of line segments in the plane, we say that a region is a {\em stabber} for if contains exactly one endpoin…
Geometric Biplane Graphs II: Graph Augmentation
Alfredo García, Ferran Hurtado, Matias Korman +5
We study biplane graphs drawn on a finite point set in the plane in general position. This is the family of geometric graphs whose vertex set is and which can be decomposed…
Geometric Biplane Graphs I: Maximal Graphs
Alfredo García, Ferran Hurtado, Matias Korman +5
We study biplane graphs drawn on a finite planar point set in general position. This is the family of geometric graphs whose vertex set is and can be decomposed into two pl…
Space-Efficient Hidden Surface Removal
Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
We propose a space-efficient algorithm for hidden surface removal that combines one of the fastest previous algorithms for that problem with techniques based on bit manipulation. S…
Colored Spanning Graphs for Set Visualization
Ferran Hurtado, Matias Korman, Marc van Kreveld +6
We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple…
Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)
Kevin Buchin, Irina Kostitsyna, Maarten Löffler +1
Let and be two imprecise points, given as probability density functions on , and let be a set of line segments (obstacles) in . We st…
Terrain visibility with multiple viewpoints
Ferran Hurtado, Maarten Löffler, Inês Matos +4
We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with viewpoints (or guards) located on th…
Space-Time Trade-offs for Stack-Based Algorithms
Luis Barba, Matias Korman, Stefan Langerman +2
In memory-constrained algorithms we have read-only access to the input, and the number of additional variables is limited. In this paper we introduce the compressed stack technique…
Computing a visibility polygon using few variables
Luis Barba, Matias Korman, Stefan Langerman +1
We present several algorithms for computing the visibility polygon of a simple polygon from a viewpoint inside the polygon, when the polygon resides in read-only memory and onl…
Flow Computations on Imprecise Terrains
Anne Driemel, Herman J. Haverkort, Maarten Löffler +1
We study the computation of the flow of water on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhed…
Adjacency-Preserving Spatial Treemaps
Kevin Buchin, David Eppstein, Maarten Löffler +2
Rectangular layouts, subdivisions of an outer rectangle into smaller rectangles, have many applications in visualizing spatial information, for instance in rectangular cartograms i…
On the Number of Higher Order Delaunay Triangulations
Dieter Mitsche, Maria Saumell, Rodrigo I. Silveira
Higher order Delaunay triangulations are a generalization of the Delaunay triangulation which provides a class of well-shaped triangulations, over which extra criteria can be optim…