20 citations · 64 across the 26 of their papers we have counts for
30 papers
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…
New production matrices for geometric graphs
Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira
We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulat…
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…
A Note on Flips in Diagonal Rectangulations
Jean Cardinal, Vera Sacristán, Rodrigo I. Silveira
Rectangulations are partitions of a square into axis-aligned rectangles. A number of results provide bijections between combinatorial equivalence classes of rectangulations and fam…
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…
On the Complexity of Barrier Resilience for Fat Regions
Matias Korman, Maarten Löffler, Rodrigo I. Silveira +1
In the \emph {barrier resilience} problem (introduced by Kumar {\em et al.}, Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we…
New results on stabbing segments with a polygon
José Miguel Díaz-Báñez, Matias Korman, Pablo Pérez-Lantero +3
We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon if at least one of its two endpoint…
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…