Rodrigo Ignacio Silveira

I am a Marie Curie postdoctoral researcher at the UPC Computational Geometry Group, headed by Ferran Hurtado. I did my PhD at Utrecht University, under the supervision of Marc van Kreveld. Before going to Utrecht for my PhD, I studied at the Computer Science Department of the Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires.

Research interests

Computational geometry

Computational geometry deals with finding efficient algorithmic solutions for geometric problems. I am currently involved in a project titled Geometric Optimization with Geometric Constraints. Its main goal is to study multiple criteria geometric problems, mainly motivated by GIS and cartography. One of them is finding triangulations to model terrains in a realistic way. Terrains are often represented by point sets, which in turn are triangulated to get a continuous model of the terrain. Many different triangulations of the same point set exist, but not all of them result in "nice looking" terrains. One of the subprojects I am working on aims at finding algorithms to compute triangulations that result on terrains with a "natural look" or with "natural properties".

One way in which we are trying to accomplish this is by the use of higher order Delaunay triangulations, which are a family of well-shaped triangulations that generalize the well-known Delaunay triangulation. In particular, we are studying optimization problems over order-k Delaunay triangulations.

My PhD thesis, titled "Optimization of polyhedral terrains", deals with several problems related to the optimization of triangulations for terrain modeling.

Geographic Information Science (GISc)

I am particularly interested in problems that arise in geographic information science and require geometric algorithms. The problems related to the optimization of triangulations for terrain modeling are examples of such. In addition, I have worked on several other problems motivated from GISc. The topics studied include algorithms for the detection of disease clusters in aggregated data (see [C4]), the detection of hot-spots (high-crime areas) in road networks (see [J9]), and the extension of road networks with incomplete data (see [C10]). The common denominator of these different topics is that they all deal with geometric objects, and often one can apply tools from computational geometry to solve the problems efficiently.

Graph drawing

The goal of graph drawing is as simple as finding algorithms to compute nice drawings of graphs. Here nice has to do with the idea of "aesthetically pleasant" drawings. It is a very interesting field related to information visualization, computational geometry and graph theory, among others fields of computer science.

As a part of my Master's thesis, supervised by Manuel Abellanas and Gregorio Hernández Peñalver (from Universidad Politécnica de Madrid), I studied force directed methods for graph drawing. We also studied the specific problem arising when the vertices of the graph represent geographical regions, such as the provinces of a country. This was an unexplored problem that turned out to be quite interesting. More information on my Master's dissertation can be found in this webpage, and in the Encuentros paper listed below ([W1]).

Another very different graph drawing problem I have worked on is drawing tanglegrams. Tanglegrams are pairs of trees, whose nodes represent objects, that have the same set of objects as leaves. Often these two trees represent hierarchical relations between objects (like software packages), and need to be drawn in front of each other, with an edge connecting the appearances of each object in both trees. A natural problem is drawing the trees in such a way that the number of crossings between the inter-tree edges is minimized. Together with several other colleagues, we have studied the particular case of complete binary trees (see [J10] for the full article).

Publications

Journal articles

[J15] C. Gray, F. Kammer, M. Löffler and R. I. Silveira. Removing Local Extrema from Imprecise Terrains. Computational Geometry: Theory and Applications 45:334-349, 2012. Download from publisher.

[J14] K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, R.I. Silveira, C. Wenk and L. Wiratma. Median Trajectories. Algorithmica, In Press (accepted 2012).

[J13] K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo and R.I. Silveira. Processing aggregated data: the location of clusters in health data. GeoInformatica 16:497-521, 2012. Download from publisher.

[J12] B. Aronov, K. Buchin, M. Buchin, B. Jansen, T. de Jong, M. van Kreveld, M. Löffler, J. Luo, R.I. Silveira and B. Speckmann. Connect the dot: Computing feed-links for network extension . Journal of Spatial Information Science 3:3-31, 2011.

[J11] D. Mitsche, M. Saumell and R. I. Silveira. On the Number of Higher Order Delaunay Triangulations . Theoretical Computer Science 412(29):3589-3597, 2011. Download from publisher.

[J10] K. Buchin, M. Buchin, J. Byrka, M. Nöllenburg, Y. Okamoto, R. I. Silveira and A. Wolff. Drawing (Complete) Binary Tanglegrams - Hardness, Approximation, Fixed-Parameter Tractability. Algorithmica 62:309-332, 2012. Download from publisher.

[J9] K. Buchin, S. Cabello, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R. I. Silveira, B. Speckmann and T. Wolle. Finding the Most Relevant Fragments in Networks. Journal of Graph Algorithms and Applications 14(2):307-336, 2010.

[J8] M. van Kreveld and R. I. Silveira. Embedding Rivers in Triangulated Irregular Networks with Linear Programming. International Journal of Geographical Information Science 25(4):615-631, 2011. Download from publisher.

[J7] B. Aronov, M. van Kreveld, M. Löffler and R. I. Silveira. Peeling Meshed Potatoes. Algorithmica 60(2):349-367, 2011. Download from publisher.

[J6] C. Gray, M. Loffler and R. I. Silveira. Smoothing imprecise 1.5D terrains. International Journal of Computational Geometry and Applications 20(4):381-414, 2010. Download from publisher.

[J5] M. van Kreveld, M. Löffler and R. I. Silveira. Optimization for first order Delaunay triangulations. Computational Geometry: Theory and Applications 43(4):377-394, 2010. Download from publisher.

[J4] R. I. Silveira and M. van Kreveld. Towards a Definition of Higher Order Constrained Delaunay Triangulations. Computational Geometry: Theory and Applications 42(4):322-337, 2009. Download from publisher.

[J3] R. I. Silveira and R. van Oostrum. Flooding countries and destroying dams. International Journal of Computational Geometry and Applications 20(3):361-380, 2010. Download from publisher.

[J2] M. G. Borgelt, M. van Kreveld, M. Löffler, J. Luo, D. Merrick, R. I. Silveira and M. Vahedi. Planar Bichromatic Minimum Spanning Trees. Journal of Discrete Algorithms 7(4):469-478, 2009. Download from publisher.

[J1] R. I. Silveira and M. van Kreveld. Optimal Higher Order Delaunay Triangulations of Polygons. Computational Geometry: Theory and Applications 42(8):803-813, 2009. Download from publisher.

Peer-reviewed conference papers

[C17] E. Arkin, J.M. Díaz-Báñez, F. Hurtado, P. Kumar, J. Mitchell, B. Palop, P. Pérez-Lantero, M. Saumell and R.I. Silveira. Bichromatic 2-center of pairs of points. In Proc. 10th Latin American Theoretical Informatics Symposium (LATIN), to appear.

[C16] L. Barba, M. Korman, S. Langerman and R. I. Silveira. Computing a visibility polygon using few variables. In Proc. 22nd International Symposium on Algorithms and Computation (ISAAC), pages 70-79, 2011. Download from publisher.

[C15] A. Driemel, H. Haverkort, M. Löffler and R. I. Silveira. Flow Computations on Imprecise Terrains. In Proc. 12th Algorithms and Data Structures Symposium (WADS), pages 350-361, 2011. Download from publisher

[C14] K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg and R. I. Silveira. Adjacency-Preserving Spatial Treemaps. In Proc. 12th Algorithms and Data Structures Symposium (WADS), pages 159-170, 2011. Download from publisher

[C13] K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, R. I. Silveira, C. Wenk and L. Wiratma. Median Trajectories. In Proc. 18th European Symposium on Algorithms (ESA), pages 463-474, 2010. Download from publisher

[C12] P. Agarwal, B. Aronov, M. van Kreveld, M. Löffler and R. I. Silveira. Computing Similarity between Piecewise-Linear Functions. In Proc. 26th ACM Symposium on Computational Geometry (SoCG), pages 375-383, 2010. Download from publisher

[C11] D. Mitsche, M. Saumell and R. I. Silveira. On the Number of Higher Order Delaunay Triangulations. In Proc. 7th International Conference on Algorithms and Complexity (CIAC), pages 217-228, 2010. Download from publisher

[C10] B. Aronov, K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo, R. I. Silveira and B. Speckmann. Connect the Dot: Computing Feed-links with Minimum Dilation. In Proc. Algorithms and Data Structures Symposium (WADS), pages 49-60, 2009. Download from publisher

[C9] M. van Kreveld and R. I. Silveira. Embedding Rivers in Polyhedral Terrains. In Proc. 25th ACM Symposium on Computational Geometry (SoCG), pages 169-178, 2009. Download from publisher

[C8] K. Buchin, S. Cabello, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R. I. Silveira, B. Speckmann and T. Wolle. Detecting Hotspots in Geographic Networks. In Advances in GIScience. Proceedings of the 12th AGILE Conference, pages 217-231, 2009. Winner of Best Paper Award. Download from publisher.

[C7] B. Aronov, K. Buchin, M. Buchin, B. Jansen, T. de Jong, M. van Kreveld, M. Löffler, J. Luo, R. I. Silveira and B. Speckmann. Feed-links for Network Extensions. In Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), pages 308-316, 2008.

[C6] C. Gray, M. Löffler and R. I. Silveira. Smoothing Imprecise 1.5D Terrains. In Proc. 6th Workshop on Approximation and Online Algorithms (WAOA), pages 214-226, 2009. Download from publisher

[C5] K. Buchin, M. Buchin, J. Byrka, M. Nöllenburg, Y. Okamoto, R. I. Silveira and A. Wolff. Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. In Proc. 16th International Symposium on Graph Drawing (GD), pages 324-335, 2009. Download from publisher. Download full version.

[C4] K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo and R. I. Silveira. Clusters in Aggregated Health Data. In Headway in Spatial Data Handling. 13th International Symposium on Spatial Data Handling (SDH), pages 77-90, 2008. Download from publisher

[C3] R. I. Silveira and M. van Kreveld. Optimal Higher Order Delaunay Triangulations of Polygons. In Proc. 8th Latin American Theoretical Informatics Symposium (LATIN), pages 133-145, 2008. Download from publisher

[C2] R. I. Silveira and R. van Oostrum. Flooding countries and destroying dams. In Proc. 10th Workshop on Algorithms and Data Structures (WADS), pages 227-238, 2007.

[C1] M. van Kreveld, M. Löffler, and R. I. Silveira. Optimization for First Order Delaunay Triangulations. In Proc. 10th Workshop on Algorithms and Data Structures (WADS), pages 175-187, 2007.

Weakly-reviewed conference papers and workshop abstracts

[W12] M. Abellanas, M. Claverol, G. Hernández, F. Hurtado, V. Sacristán, M. Saumell and R. I. Silveira. Improving shortest paths in the Delaunay triangulation. In XIV Spanish Meeting on Computational Geometry, pages 117-120, 2011.

[W11] A. Driemel, H. Haverkort, M. Löffler and R. I. Silveira. Flow Computations on Imprecise Terrains. In Abstracts 27th European Workshop on Computational Geometry (EuroCG), pages 119-122, 2011.

[W10] M. Abellanas, M. Claverol, G. Hernández, F. Hurtado, V. Sacristán, M. Saumell and R. I. Silveira. Improving shortest paths in the Delaunay triangulation. In Abstracts 27th European Workshop on Computational Geometry (EuroCG), pages 43-46, 2011.

[W9] C. Gray, F. Kammer, M. Löffler and R. I. Silveira. Removing Local Extrema from Imprecise Terrains . In Abstracts 26th European Workshop on Computational Geometry (EuroCG), pages 181-184, 2010. Download full version.

[W8] C. Gray, M. Löffler and R. I. Silveira. Minimizing Slope Change in Imprecise 1.5D terrains. In Proc. 21st Canadian Conference on Computational Geometry (CCCG), pages 55-58, 2009.

[W7] P. Agarwal, B. Aronov, M. van Kreveld, M. Löffler and R. I. Silveira. Matching Terrains under a Linear Transformation. In Abstracts 25th European Workshop on Computational Geometry (EuroCG), pages 109-112, 2009.

[W6] C. Gray, M. Löffler and R. I. Silveira. Smoothing imprecise 1-dimensional terrains. In Abstracts 24th European Workshop on Computational Geometry (EuroCG), pages 141-144, 2008.

[W5] B. Aronov, M. van Kreveld, M. Löffler and R. I. Silveira. Largest Subsets of Triangles in a Triangulation. In Proc. 19th Canadian Conference on Computational Geometry (CCCG), pages 213-216, 2007.

[W4] R. I. Silveira and M. van Kreveld. Towards a Definition of Higher Order Constrained Delaunay Triangulations. In Proc. 19th Canadian Conference on Computational Geometry (CCCG), pages 161-164, 2007.

[W3] R. I. Silveira and M. van Kreveld. Optimal Higher Order Delaunay Triangulations of Polygons. In Abstracts 23rd European Workshop on Computational Geometry (EuroCG), pages 194-197, 2007.

[W2] M. G. Borgelt, M. van Kreveld, M. Löffler, J. Luo, D. Merrick, R. I. Silveira and M. Vahedi. Planar Bichromatic Minimum Spanning Trees. In Abstracts 23rd European Workshop on Computational Geometry (EuroCG), pages 162-165, 2007.

[W1] M. Abellanas, A. Aiello, G. Hernández and R. I. Silveira Network drawing with geographical constraints on vertices. In Actas XI Encuentros de Geometría Computacional, pages 111-118 , 2005.

Theses

[T2] R. I. Silveira Optimization of polyhedral terrains. PhD thesis. Supervisor: Marc van Kreveld. Utrecht University, 2009.

[T1] A. Aiello and R. I. Silveira Force-directed graph drawing: review of the state-of-the-art and proposal of new algorithms for graphs where vertices represent geographical regions. Master's thesis (in Spanish). Supervisors: Manuel Abellanas and Gregorio Hernández Peñalver. Universidad de Buenos Aires, 2004.