Silveira, Rodrigo Ignacio
Total activity: 55
Department
Department of Applied Mathematics II
E-mail
rodrigo.silveiraupc.edu
Contact details
UPC directory Open in new window
Orcid
0000-0003-0202-4543 Open in new window
Scopus Author ID
23398643600 Open in new window

Graphic summary
  • Show / hide key
  • Information


Scientific and technological production
  •  

1 to 50 of 55 results
  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

    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.

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

    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.

  • Access to the full text
    Flow computations on imprecise terrains  Open access

     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

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    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.

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

    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.

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

    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.

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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).

    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).

  • Access to the full text
    Median trajectories  Open access

     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

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    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)

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

  • Access to the full text
    Removing local extrema from imprecise terrains  Open access

     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

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    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.

  • Access to the full text
    Improving shortest paths in the Delaunay triangulation  Open access

     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

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    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.

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • MATHEMATICAL FOUNDATIONS OF HIGH QUALITY TERRAIN MODELS

     Silveira, Rodrigo Ignacio; Hurtado Diaz, Fernando Alfredo
    Competitive project

     Share

  • 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; Hurtado Diaz, Fernando Alfredo
    Competitive project

     Share

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Adjacency-preserving spatial treemaps

     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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Access to the full text
    Computing similarity between piecewise-linear functions  Open access

     Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; 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

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    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.

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

     Share

  • Optimization of polyhedral terrains

     Silveira, Rodrigo Ignacio
    Utrecht University
    Theses

     Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Embedding rivers in polyhedral terrains

     Kreveld, Marc van; Silveira, Rodrigo Ignacio
    ACM Annual Symposium on Computational Geometry
    p. 169-178
    DOI: 10.1145/1542362.1542398
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Detecting hotspots in geographic networks

     Buchin, Kevin; Cabello, Sergio; Gudmundsson, Joachim; Löffler, Maarten; Luo, Jun; Rote, Günter; Silveira, Rodrigo Ignacio; Speckmann, Bettina; Wolle, Thomas
    AGILE International Conference on Geographic Information Science
    p. 217-231
    DOI: 10.1007/978-3-642-00318-9_11
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Minimizing slope change in imprecise 1.5D terrains

     Gray, Chris; Löffler, Maarten; Silveira, Rodrigo Ignacio
    Canadian Conference on Computational Geometry
    p. 55-58
    Presentation's date: 2009
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Matching terrains under a linear transformation

     Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
    European Workshop on Computational Geometry
    p. 109-112
    Presentation's date: 2009
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Smoothing imprecise 1.5D terrains

     Gray, Chris; Löffler, Maarten; Silveira, Rodrigo Ignacio
    Workshop on Approximation and Online Algorithms
    p. 214-226
    DOI: 10.1007/978-3-540-93980-1_17
    Presentation's date: 2009
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • 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

    View View Open in new window  Share Reference managers Reference managers Open in new window

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

     Buchin, Kevin; Buchin, M.; Byrka, Jaroslaw; Nöllenburg, Martin; Okamoto, Yoshio; Silveira, Rodrigo Ignacio; Wolff, Alexander
    Symposium on Graph Drawing
    p. 324-335
    DOI: 10.1007/978-3-642-00219-9_32
    Presentation's date: 2008
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Clusters in aggregated health data

     Buchin, Kevin; Buchin, M.; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio
    International Symposium on Spatial Data Handling
    p. 77-90
    DOI: 10.1007/978-3-540-68566-1_5
    Presentation's date: 2008
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Feed-links for network extensions

     Aronov, Boris; Buchin, Kevin; Buchin, Maike; Jansen, Bart; De Jong, Tom; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio; Speckmann, Bettina
    ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
    p. 308-316
    DOI: 10.1145/1463434.1463478
    Presentation's date: 2008
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Smoothing imprecise 1-dimensional terrains

     Gray, Chris; Löffler, Maarten; Silveira, Rodrigo Ignacio
    European Workshop on Computational Geometry
    p. 141-144
    Presentation's date: 2008
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Optimal higher order delaunay triangulations of polygons

     Silveira, Rodrigo Ignacio; Kreveld, Marc van
    Latin American Theoretical Informatics Symposium
    p. 133-145
    DOI: 10.1007/978-3-540-78773-0_12
    Presentation's date: 2008
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Towards a definition of higher order constrained delaunay triangulations

     Silveira, Rodrigo Ignacio; Kreveld, Marc van
    Canadian Conference on Computational Geometry
    p. 161-164
    Presentation's date: 2007
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Flooding countries and destroying dams

     Silveira, Rodrigo Ignacio; Van Oostrum, René
    Workshop on Algorithms and Data Structures
    p. 227-238
    DOI: 10.1007/978-3-540-73951-7_21
    Presentation's date: 2007
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window