Silveira, Rodrigo Ignacio
Total activity: 67

## Scientific and technological production Ordered by:  Date asc. Date desc. Title asc. Title desc. Researcher asc. Researcher desc.

1 to 50 of 67 results
• New results on stabbing segments with a polygon

Díaz Bañez, José Miguel; Korman Cozzetti, Matias; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
Computational geometry: theory and applications
Vol. 48, num. 1, p. 14-29
DOI: 10.1016/j.comgeo.2014.06.002
Date of publication: 2015-01-01
Journal article

We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s is stabbed by a simple polygon P if at least one endpoint of s is contained in P, and a segment set S is stabbed by P if P stabs every element of S. Given a segment set S, we study the problem of finding a simple polygon P stabbing S in a way that some measure of P (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by Loftier and van Kreveld [Algorithmica 56(2), 236-269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard. (C) 2014 Elsevier B.V. All rights reserved.

• Balanced partitions of 3-colored geometric sets in the plane

Bereg, Sergey; Hurtado, Ferran; Kano, Mikio; Korman, Matias; Lara, Dolores; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio; Urrutia Galicia, Jorge; Verbeek, Kevin
Discrete applied mathematics
Vol. 181, p. 21-32
DOI: 10.1016/j.dam.2014.10.015
Date of publication: 2015
Journal article

Let SS be a finite set of geometric objects partitioned into classes or colors . A subset S'¿SS'¿S is said to be balanced if S'S' contains the same amount of elements of SS from each of the colors. We study several problems on partitioning 33-colored sets of points and lines in the plane into two balanced subsets: (a) We prove that for every 3-colored arrangement of lines there exists a segment that intersects exactly one line of each color, and that when there are 2m2m lines of each color, there is a segment intercepting mm lines of each color. (b) Given nn red points, nn blue points and nn green points on any closed Jordan curve ¿¿, we show that for every integer kk with 0=k=n0=k=n there is a pair of disjoint intervals on ¿¿ whose union contains exactly kk points of each color. (c) Given a set SS of nn red points, nn blue points and nn green points in the integer lattice satisfying certain constraints, there exist two rays with common apex, one vertical and one horizontal, whose union splits the plane into two regions, each one containing a balanced subset of SS.

• Computing a visibility polygon using few variables

Barba, Luis; Korman Cozzetti, Matias; Langerman, Stefan; Silveira, Rodrigo Ignacio
Computational geometry: theory and applications
Vol. 47, num. 9, p. 918-926
DOI: 10.1016/j.comgeo.2014.04.001
Date of publication: 2014-10-01
Journal article

We present several algorithms for computing the visibility polygon of a simple polygon P of n vertices (out of which r are reflex) from a viewpoint inside P, when P resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O (n (r) over bar) time, where (r) over bar denotes the number of reflex vertices of P that are part of the output. Whenever we are allowed to use O(s) variables, the running time decreases to O (nr/2(s) + n log(2) r) (or O (nr/2(s) + n log r) randomized expected time), where s is an element of O (log r). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained. (C) 2014 Elsevier B.V. All rights reserved.

• 2014SGR46 - GRUP DE RECERCA EN GEOMETRIA COMPUTACIONAL I MATEMÀTICA DISCRETA

Noy Serrano, Marcos; Brunat Blay, Josep Maria; Claverol Aguas, Merce; Dall, Aaron Matthew; Hernando Martin, Maria Del Carmen; Huemer, Clemens; Maureso Sanchez, Montserrat; De Mier Vinue, Anna; Mora Gine, Mercè; Pfeifle, Julian Thoralf; Sacristán Adinolfi, Vera; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
Competitive project

• Bichromatic 2-center of pairs of points

Arkin, Esther M.; Díaz Bañez, José Miguel; Hurtado, Ferran; Kumar, Piyush; Mitchell, Joseph S. B.; Palop, Belén; Pérez Lantero, Pablo; Saumell, Maria; Silveira, Rodrigo Ignacio
Computational geometry: theory and applications
Vol. 48, num. 2, p. 94-107
DOI: 10.1016/j.comgeo.2014.08.004
Date of publication: 2014
Journal article

We study a class of geometric optimization problems closely related to the 2-center problem: Given a set S of n pairs of points in the plane, for every pair, we want to assign red color to a point of the pair and blue color to the other point in order to optimize the radii of the minimum enclosing ball of the red points and the minimum enclosing ball of the blue points. In particular, we consider the problems of minimizing the maximum and minimizing the sum of the two radii of the minimum enclosing balls. For each case, minmax and minsum, we consider distances measured in the L2L2 and in the L8L8 metrics.

• Cell-paths in mono- and bichromatic line arrangements in the plane

Aichholzer, Oswin; Cardinal, Jean; Hackl, Thomas; Hurtado, Ferran; Korman, Matias; Pilz, Alexander; Silveira, Rodrigo Ignacio; Uehara, Ryuhei; Valtr, Pavel; Vogtenhuber, Birgit; Welzl, Emo
Discrete mathematics and theoretical computer science
Vol. 16, num. 3, p. 317-332
Date of publication: 2014
Journal article

We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n2/4. Further, we show that in every arrangement of n red and blue lines — in general position and not all of the same color — there is a simple path through at least n cells where red and blue lines are crossed alternatingly.

• Colored ray configurations

Fabila Monroy, Ruy; Garcia Olaverri, Alfredo Martin; Hurtado, Ferran; Jaume, Rafel; Pérez Lantero, Pablo; Saumell, Maria; Silveira, Rodrigo Ignacio; Tejel Altarriba, Francisco Javier; Urrutia Galicia, Jorge
p. 401-406
Presentation's date: 2014
Presentation of work at congresses

We study the cyclic sequences induced at innity by pairwise-disjoint colored rays with apices on a given bal- anced bichromatic point set, where the color of a ray is inherited from the color of its apex. We derive a lower bound on the number of color sequences that can be realized from any xed point set. We also examine se- quences that can be realized regardless of the point set and exhibit negative examples as well. In addition, we provide algorithms to decide whether a sequence is re- alizable from a given point set on a line or in convex position

We study the cyclic sequences induced at in nity by pairwise-disjoint colored rays with apices on a given bal- anced bichromatic point set, where the color of a ray is inherited from the color of its apex. We derive a lower bound on the number of color sequences that can be realized from any xed point set. We also examine se- quences that can be realized regardless of the point set and exhibit negative examples as well. In addition, we provide algorithms to decide whether a sequence is re- alizable from a given point set on a line or in convex position

• A faster algorithm to compute the visibility map of a 1.5D terrain

Löffler, Maarten; Saumell, Maria; Silveira, Rodrigo Ignacio
European Workshop on Computational Geometry
p. 1-4
Presentation's date: 2014
Presentation of work at congresses

Given a 1.5D terrain, i.e., an x -monotone polygonal line in R 2 with n vertices, and 1 m n viewpoints placed on some of the terrain vertices, we study the problem of computing the parts of the terrain that are visible from at least one of the viewpoints. We present an algorithm that runs in O ( n + m log m ) time. This improves over a previous algorithm recently proposed

Given a 1.5D terrain, i.e., an x -monotone polygonal line in R 2 with n vertices, and 1 m n viewpoints placed on some of the terrain vertices, we study the problem of computing the parts of the terrain that are visible from at least one of the viewpoints. We present an algorithm that runs in O ( n + m log m ) time. This improves over a previous algorithm recently proposed

• Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Buchin, Kevin; Kostitsyna, Irina; Löffler, Maarten; Silveira, Rodrigo Ignacio
European Workshop on Computational Geometry
p. 1-4
Presentation's date: 2014
Presentation of work at congresses

Let p and q be two imprecise points, given as prob- ability density functions on R 2 , and let R be a set of n line segments in R 2 . We study the problem of approximating the probability that p and q can see each other; that is, that the segment connecting p and q does not cross any segment of R . To solve this problem, we approximate each density function by a weighted set of polygons; a novel approach to dealing with probability density functions in computational geometry

• Terrain visibility with multiple viewpoints

Hurtado Diaz, Fernando Alfredo; Löffler, Maarten; Matos, Inés P.; Sacristán Adinolfi, Vera; Saumell, Maria; Silveira, Rodrigo Ignacio; Staals, Frank
International Symposium on Algorithms and Computation
p. 317-327
DOI: 10.1007/978-3-642-45030-3_30
Presentation's date: 2013-12-17
Presentation of work at congresses

We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider three fundamental visibility structures: the visibility map, the colored visibility map, and the Voronoi visibility map. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting.

Postprint (author’s final draft)

• Stabbing Segments with Rectilinear Objects

Claverol Aguas, Merce; Seara Ojea, Carlos; Garijo, Delia; Korman Cozzetti, Matias; Silveira, Rodrigo Ignacio
Mexican Conference on Discrete Mathematics and Computational Geometry
p. 211-221
Presentation's date: 2013-11-13
Presentation of work at congresses

Given a set of n line segments in the plane, we say that a region R of the plane is a stabber if R contains exactly one end point of each segment of the set. In this paper we provide efficient algorithms for determining wheter or not a stabber exists for several shapes of stabbers. Specially, we consider the case in which the stabber can be described as the intersecction of isothetic halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3-sided rectangles, or rectangles). We provided efficient algorithms reporting all combinatorially different stabbers of the shape. The algorithms run in O(n) time (for the halfplane case), O(n logn) time (for strips and quadrants), O(n^2) (for 3-sided rectangles), or O(n^3) time (for rectangles).

• Geometric biplane graphs I: maximal graphs

Garcia Olaverri, Alfredo Martin; Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Matos, Inés P.; Saumell, Maria; Silveira, Rodrigo Ignacio; Tejel Altarriba, Francisco Javier; Tóth, Csaba D.
Mexican Conference on Discrete Mathematics and Computational Geometry
p. 123-134
Presentation's date: 2013-11-11
Presentation of work at congresses

• Colored spanning graphs for set visualization

Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Van Kreveld, Matias; Löffler, Maarten; Sacristán Adinolfi, Vera; Silveira, Rodrigo Ignacio; Speckmann, Bettina
Symposium on Graph Drawing
p. 280-291
DOI: 10.1007/978-3-319-03841-4_25
Presentation's date: 2013-09
Presentation of work at congresses

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. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem is NP-hard. Hence we give an (1/2¿+1)-approximation, where ¿ is the Steiner ratio. We also present efficient exact solutions if the points are located on a line or a circle. Finally we consider extensions to more than two sets.

• Cell-paths in mono- and bichromatic line arrangements in the plane

Aichholzer, Oswin; Cardinal, Jean; Hackl, Thomas; Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Pilz, Alexander; Silveira, Rodrigo Ignacio; Uehara, Ryuhei; Vogtenhuber, Birgit; Welzl, Emo
p. 169-174
Presentation's date: 2013-08-09
Presentation of work at congresses

• New results on stabbing segments with a polygon

Díaz Bañez, José Miguel; Korman Cozzetti, Matias; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
International Conference on Algorithms and Complexity
p. 146-157
DOI: 10.1007/978-3-642-38233-8_13
Presentation's date: 2013-05
Presentation of work at congresses

We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments.

• MORFOLOGIA GEOMETRICA COMPUTACIONAL

Trias Pairo, Juan; Pfeifle, Julian Thoralf; Mora Gine, Mercè; Hernando Martin, Maria Del Carmen; Huemer, Clemens; Seara Ojea, Carlos; Korman Cozzetti, Matias; Sacristán Adinolfi, Vera; Silveira, Rodrigo Ignacio; Claverol Aguas, Merce; Dall, Aaron Matthew; Hurtado Diaz, Fernando Alfredo
Competitive project

• Flow computations on imprecise terrains

Driemel, Anne; Haverkort, Herman; Löffler, Maarten; Silveira, Rodrigo Ignacio
Journal of Computational Geometry
Vol. 4, num. 1, p. 38-78
Date of publication: 2013
Journal article

We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predened graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x; y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, or a set of vertices, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time.

We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a prede ned graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x; y)-coordinates are fi xed. For the fi rst model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, or a set of vertices, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time.

• Computing correlation between piecewise-linear functions

Agarwal, Pankaj; Aronov, Boris; Van Kreveld, Matias; Löffler, Maarten; Silveira, Rodrigo Ignacio
SIAM journal on computing
Vol. 42, num. 5, p. 1867-1887
DOI: 10.1137/120900708
Date of publication: 2013
Journal article

We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in $O(n^{4/3}\operatorname{polylog}n)$ expected time, where $n$ is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a $(1+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain.

• Removing local extrema from imprecise terrains

Gray, Chris; Kammer, Frank; Löffler, Maarten; Silveira, Rodrigo Ignacio
Computational geometry: theory and applications
Vol. 45, num. 7, p. 334-349
DOI: 10.1016/j.comgeo.2012.02.002
Date of publication: 2012-08
Journal article

In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain; that is, fi nding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in O(n log n) time, for a terrain with n vertices. Interestingly, however, the problem of fi nding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of O(log log n) unless P = NP. Moreover, we show that even a simpli ed version of the problem where we can have only three di fferent types of intervals for the vertices is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community.

• Processing aggregated data : the location of clusters in health data

Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio
Geoinformatica
Vol. 16, num. 3, p. 497-521
DOI: 10.1007/s10707-011-0143-6
Date of publication: 2012-07
Journal article

Spatially aggregated data is frequently used in geographical applications. Often spatial data analysis on aggregated data is performed in the same way as on exact data, which ignores the fact that we do not know the actual locations of the data. We here propose models and methods to take aggregation into account. For this we focus on the problem of locating clusters in aggregated data. More specifically, we study the problem of locating clusters in spatially aggregated health data. The data is given as a subdivision into regions with two values per region, the number of cases and the size of the population at risk. We formulate the problem as finding a placement of a cluster window of a given shape such that a cluster function depending on the population at risk and the cases is maximized. We propose area-based models to calculate the cases (and the population at risk) within a cluster window. These models are based on the areas of intersection of the cluster window with the regions of the subdivision. We show how to compute a subdivision such that within each cell of the subdivision the areas of intersection are simple functions. We evaluate experimentally how taking aggregation into account influences the location of the clusters found.

• Median trajectories

Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio; Wenk, Carola; Wiratma, Lionov
Algorithmica
p. 1-20
Date of publication: 2012-05
Journal article

We investigate the concept of a median among a set of trajectories. We establish criteria that a “median trajectory” should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worst-case running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and evaluate whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better.

Postprint (author’s final draft)

• Bichromatic 2-center of pairs of points

Arkin, Esther M.; Díaz Bañez, José Miguel; Hurtado Diaz, Fernando Alfredo; Kumar, Piyush; Mitchell, Joseph S. B.; Palop, Belén; Pérez Lantero, Pablo; Saumell, Maria; Silveira, Rodrigo Ignacio
Latin American Symposium on Theoretical Informatics
p. 25-36
DOI: 10.1007/978-3-642-29344-3_3
Presentation's date: 2012-04-19
Presentation of work at congresses

• Drawing (complete) binary tanglegrams hardness, approximation, fixed-parameter tractability

Buchin, Kevin; Buchin, Maike; Byrka, Jaroslaw; Noellenburg, Martin; Okamoto, Yoshio; Silveira, Rodrigo Ignacio; Wolff, Alexander
Algorithmica
Vol. 62, num. 1-2, p. 309-332
DOI: 10.1007/s00453-010-9456-3
Date of publication: 2012-02
Journal article

• Improving shortest paths in the Delaunay triangulation

Claverol Aguas, Merce; Hernández Peñalver, Gregorio; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell, Maria; Silveira, Rodrigo Ignacio; Abellanas, Manuel
International journal of computational geometry and applications
Vol. 22, num. 6, p. 559-576
DOI: 10.1142/S0218195912500161
Date of publication: 2012
Journal article

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set S, we look for a new point p ¿ S that can be added, such that the shortest path from s to t, in the Delaunay triangulation of S¿{p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest path from s to t, in the Delaunay triangulation of P ∪ {p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

• Connect the dot: computing feed-links for network extension

Aronov, Boris; Buchin, Kevin; Buchin, Maike; Jansen, Bart; De Jong, Tom; Kreveld, Marc van; Loffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio; Speckmann, Bettina
Journal of Spatial Information Science
num. 3, p. 3-31
DOI: 10.5311/JOSIS.2011.3.47
Date of publication: 2011-12-20
Journal article

Road network analysis can require distance from points that are not on the network themselves. We study the algorithmic problem of connecting a point inside a face (region) of the road network to its boundary while minimizing the detour factor of that point to any point on the boundary of the face. We show that the optimal single connection (feed-link) can be computed in O(λ7(n) log n) time, where n is the number of vertices that bounds the face and λ7(n) is the slightly superlinear maximum length of a Davenport- Schinzel sequence of order 7 on n symbols. We also present approximation results for placing more feed-links, deal with the case that there are obstacles in the face of the road network that contains the point to be connected, and present various related results.

• Computing a visibility polygon using few variables

Barba, Luis; Korman Cozzetti, Matias; Langerman, Stefan; Silveira, Rodrigo Ignacio
International Symposium on Algorithms and Computation
p. 70-79
DOI: 10.1007/978-3-642-25591-5_9
Presentation's date: 2011-12-05
Presentation of work at congresses

• Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)

Claverol Aguas, Merce; Dall, Aaron Matthew; Silveira, Rodrigo Ignacio; Huemer, Clemens; Mora Gine, Mercè; Sacristán Adinolfi, Vera; Hernando Martin, Maria Del Carmen; Seara Ojea, Carlos; Montes Lozano, Antonio; Pfeifle, Julian Thoralf; Korman Cozzetti, Matias; Hurtado Diaz, Fernando Alfredo
Competitive project

Buchin, Kevin; Eppstein, David; Löffler, Maarten; Nöllenburg, Martin; Silveira, Rodrigo Ignacio
Workshop on Algorithms and Data Structures
p. 159-170
DOI: 10.1007/978-3-642-22300-6_14
Presentation's date: 2011-08-16
Presentation of work at congresses

• Flow computations on imprecise terrains

Driemel, Anne; Haverkort, Herman; Löffler, Maarten; Silveira, Rodrigo Ignacio
Workshop on Algorithms and Data Structures
p. 350-361
DOI: 10.1007/978-3-642-22300-6_30
Presentation's date: 2011-08-15
Presentation of work at congresses

We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x, y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time.

• MATHEMATICAL FOUNDATIONS OF HIGH QUALITY TERRAIN MODELS

Competitive project

• On the number of higher order Delaunay triangulations

Mitsche, Dieter Wilhelm; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio
Theoretical computer science
Vol. 412, num. 29, p. 3589-3597
DOI: 10.1016/j.tcs.2011.03.005
Date of publication: 2011-07-01
Journal article

• Improving shortest paths in the Delaunay triangulation

Claverol Aguas, Merce; Hernández, Gregorio; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio; Abellanas, Manuel
Spanish Meeting on Computational Geometry
p. 117-120
Presentation's date: 2011-06-28
Presentation of work at congresses

• Improving shortest paths in the Delaunay triangulation

Claverol Aguas, Merce; Hernández Peñalver, Gregorio; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio; Abellanas, Manuel
European Workshop on Computational Geometry
p. 43-46
Presentation's date: 2011-03-28
Presentation of work at congresses

• Flow computations on imprecise terrains

Driemel, Anne; Haverkort, Herman; Loffler, Maarten; Silveira, Rodrigo Ignacio
European Workshop on Computational Geometry
p. 119-122
Presentation's date: 2011-03-28
Presentation of work at congresses

• Embedding rivers in triangulated irregular networks with linear programming

Kreveld, Marc van; Silveira, Rodrigo Ignacio
International journal of geographical information science
Vol. 25, num. 4, p. 615-631
DOI: 10.1080/13658816.2010.488240
Date of publication: 2011
Journal article

• Peeling meshed potatoes

Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Algorithmica
Vol. 60, num. 2, p. 349-367
DOI: 10.1007/s00453-009-9346-8
Date of publication: 2011
Journal article

• Median trajectories

Buchin, Kevin; Buchin, M.; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio; Wenk, Carola; Wiratma, Lionov
European Symposium on Algorithms
p. 463-474
DOI: 10.1007/978-3-642-15775-2_40
Presentation's date: 2010-09-06
Presentation of work at congresses

• Smoothing imprecise 1.5D terrains

Gray, Chris; Löffler, Maarten; Silveira, Rodrigo Ignacio
International journal of computational geometry and applications
Vol. 20, num. 4, p. 381-414
DOI: 10.1142/S0218195910003359
Date of publication: 2010-08
Journal article

• Computing similarity between piecewise-linear functions

Agarwal, Pankaj; Kreveld, Marc van; Aronov, Boris; Löffler, Maarten; Silveira, Rodrigo Ignacio
ACM Annual Symposium on Computational Geometry
p. 375-383
DOI: 10.1145/1810959.1811020
Presentation's date: 2010-06-16
Presentation of work at congresses

We study the problem of computing the similarity between two piecewise-linear bivariate functions de ned over a common domain, where the surfaces they de ne in 3D|polyhedral terrains|can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4=3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1+")-approximation algorithm for minimizing the area that runs in O(n=p") time, for any xed " > 0. The (1 + ")- approximation algorithm for the bivariate version, where volume is minimized, runs in O(n="2) time, for any xed " > 0, provided the two functions are de ned over the same triangulation of their domain.

Postprint (author’s final draft)

• Finding the most relevant fragments in networks

Buchin, Kevin; Cabello, Sergio; Gudmundsson, Joachim; Löffler, Maarten; Luo, Jun; Rote, Günter; Silveira, Rodrigo Ignacio; Speckmann, Bettina; Wolle, Thomas
Journal of graph algorithms and applications
Vol. 14, num. 2, p. 307-336
Date of publication: 2010-06
Journal article

• Flooding countries and destroying dams

Silveira, Rodrigo Ignacio; Van Oostrum, René
International journal of computational geometry and applications
Vol. 20, num. 3, p. 361-380
DOI: 10.1142/S0218195910003347
Date of publication: 2010-06
Journal article

• On the number of higher order Delaunay triangulations

Mitsche, Dieter Wilhelm; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio
International Conference on Algorithms and Complexity
p. 217-228
DOI: 10.1007/978-3-642-13073-1_20
Presentation's date: 2010-05-27
Presentation of work at congresses

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 optimized. A triangulation is order-k Delaunay if the circumcircle of each triangle of the triangulation contains at most k points. In this paper we study lower and upper bounds on the number of higher order Delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order Delaunay triangulation, even for large orders, whereas for first order Delaunay triangulations, the maximum number is 2n−3. Next we show that uniformly distributed points have an expected number of at least 2ρ1n(1+o(1)) first order Delaunay triangulations, where ρ1 is an analytically defined constant (ρ1 ≈ 0.525785), and for k > 1, the expected number of order-k Delaunay triangulations (which are not order-i for any i < k) is at least 2ρkn(1+o(1)), where ρk can be calculated numerically.

• Optimization for first order Delaunay triangulations

Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Computational geometry: theory and applications
Vol. 43, num. 4, p. 377-394
DOI: 10.1016/j.comgeo.2009.01.010
Date of publication: 2010-05
Journal article

• Removing local extrema from imprecise terrains

Gray, Chris; Kammer, Frank; Löffler, Maarten; Silveira, Rodrigo Ignacio
European Workshop on Computational Geometry
p. 181-184
Presentation's date: 2010-03-24
Presentation of work at congresses

• Connect the dot: computing feed-links with minimum dilation

Aronov, Boris; Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio; Speckmann, Bettina
Workshop on Algorithms and Data Structures
p. 49-60
DOI: 10.1007/978-3-642-03367-4_5
Presentation's date: 2009-08-22
Presentation of work at congresses

• Optimization of polyhedral terrains

Silveira, Rodrigo Ignacio
Utrecht University
Theses

• Best Paper Award

Silveira, Rodrigo Ignacio; Buchin, Kevin; Cabello, Sergio; Gudmundsson, Joachim; Loffler, Maarten; Luo, Jun; Rote, Günter; Speckmann, Bettina; Wolle, Thomas
Award or recognition

• Planar bichromatic minimum spanning trees

Borgelt, Magdalene; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Merrick, Damian; Silveira, Rodrigo Ignacio; Vahedi, Mostafa
Journal of discrete algorithms
Vol. 7, num. 4, p. 469-478
DOI: 10.1016/j.jda.2008.08.001
Date of publication: 2009
Journal article

• Towards a definition of higher order constrained Delaunay triangulations

Silveira, Rodrigo Ignacio; Kreveld, Marc van
Computational geometry: theory and applications
Vol. 42, num. 4, p. 322-337
DOI: 10.1016/j.comgeo.2008.09.005
Date of publication: 2009
Journal article

• Optimal higher order Delaunay triangulations of polygons

Silveira, Rodrigo Ignacio; Kreveld, Marc van
Computational geometry: theory and applications
Vol. 42, num. 8, p. 803-813
DOI: 10.1016/j.comgeo.2008.02.006
Date of publication: 2009
Journal article