Research publications


F. Hurtado, M. Korman, M. van Kreveld, M. Löffler, V. Sacristán, A. Shioura, R. Silveira, B. Speckmann, T. Tokuyama
Colored Spanning Graphs for Set Visualization
Computational Geometry – Theory and Applications, on-line 2017, doi: 10.1016/j.comgeo.2017.06.006. Link
Preliminary version: F. Hurtado, M. Korman, M. van Kreveld, M. Löffler, V. Sacristán, R. Silveira, B. Speckmann, Colored Spanning Graphs for Set Visualization, Proc. 21st International Symposium on Graph Drawing, Bordeaux (France), September 23-25, Springer-Verlag LNCS 8242, pp. 283-294, 2013. PDF


D. Duran, V. Sacristán, R. Silveira
Map construction algorithms: an evaluation through hiking data
Proceedings of the 5th ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, S. Francisco (USA), October 31, pp. 74-83, 2016. Link


I. Parada, V. Sacristán, R. Silveira
A New Meta-Module for Efficient Reconfiguration of Hinged-Units Modular Robots
Proceedings IEEE International Conference on Robotics and Automation, Stockholm (Sweden), May 16-21, pp. 5197 – 5202, 2016. Link
Preliminary extended abstract: A new meta-module for efficient robot reconfiguration, in Abstracts XVI Spanish Meeting on Computational Geometry, Barcelona (Spain), July 1-3, pp. 53-56, 2015. PDF


J. Gudmundsson, I. Kostitsyna, M. Löffler, Vera Sacristán, Rodrigo I. Silveira
Beaconless geocast protocols are interesting, even in 1D
Abstracts of the 32nd European Workshop on Computational Geometry, Lugano (Switzerland), March 30 – April 1, pp. 227-230, 2016. PDF


E. Galan, R. Padró, I. Marco, E. Tello, G. Cunfer, G. I. Guzmán, M. González de Molina, F. Krausmann, S. Gingrich, V. Sacristán, D. Moreno
Widening the analysis of Energy Return On Investment (EROI) in agroecosystems: A proposal to study socio-ecological transitions to industrialized farm systems (the Vallès County, Catalonia, c.1860 and 1999)
Ecological Modelling, Volume 336, pp. 13-25, 2016. Link PDF


E. Tello, E. Galán, V. Sacristán, G. Cunfer, G.I. Guzmán-Casado, M. González de Molina, F. Krausmann, S. Gingrich, R. Padró, I. Marco, D. Moreno-Delgado
Opening the black box of energy throughputs in agroecosystems: a decomposition analysis of final EROI into its internal and external returns (the Vallès County, Catalonia, c.1860 and 1999)
Ecological Economics, Volume 121, pp. 160-174, 2016. Link


E. Tello, E. Galán, G. Cunfer, G.I. Guzmán-Casado, M. González de Molina, F. Krausmann, S. Gingrich, V. Sacristán, I. Marco, R. Padró, D. Moreno-Delgado
A proposal for a workable analysis of Energy Return on Investment (EROI) in agroecosystems. Part I: Analytical approach
IFF Social Ecology Working Papers 156, Vienna, 2015. Link


M. Perera, V. Sacristán
Efficient distributed and parallel reconfiguration of expand-contract modular robots
Abstracts XVI Spanish Meeting on Computational Geometry, Barcelona (Spain), July 1-3, pp. 49-52, 2015. Link


O. Aichholzer, T. Hackl, A.Pilz, P. A. Ramos, V. Sacristán, B. Vogtenhuber
Empty triangles in good drawings of the complete graph
Graphs and Combinatorics, Volume 31, Issue 2, pp. 335-345, 2015. Link
Extended abstract in Proc. 21st Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca (México), November 11-15, pp. 21-29, 2013. Preliminary version: arXiv:1306.5081 [cs.CG]


F. Hurtado, E. Molina, S. Ramaswami, V. Sacristán
Distributed reconfiguration of 2D lattice-based modular robotic systems
Autonomous Robots, Volume 38, Issue 4, pp. 383-413, 2015. Link
Extended abstract: Distributed universal reconfiguration of 2D lattice-based modular robots. Proc. 29th European Workshop on Computational Geometry, Braunschweig, Germany, March 18-20, pp. 139-142, 2013. PDF
Go to the distributed 2D reconfiguration page

V. Sacristán
Controlling modular robotic systems: some ideas from Computational Geometry
O. Cheong, J. Erickson, M. Teillaud, Computational Geometry (Dagstuhl Seminar 15111), Dagstuhl Reports, Volume 5, Issue 3, p. 53, 2015. LinkSlides


F. Hurtado, M. Löffler, I. P. Matos, V. Sacristán, M. Saumell, R. Silveira, F. Staals
Terrain visibility with multiple viewpoints
International Journal of Computational Geometry and Applications, Volume 14, Issue 4, 2014. Link
Preliminary version in Proc. 24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, December 16-18, Springer-Verlag LNCS 8283, pp. 317-327, 2013. PDF. Full version: arXiv:1309.4323 [cs.CG]


O. Aichholzer, T. Hackl, V. Sacristán, B. Vogtenhuber, R. Wallner
Simulating distributed algorithms for lattice agents
Proc. 15th Spanish Meeting on Computational Geometry, Sevilla, June 26-28, pp. 81-84, 2013. PDF
Go to the simulators page


B. Brallinger, N. Benbernou, P. Bose, M. Damian, E. D. Demaine, V. Dumivic, R. Flatland, F. Hurtado, J. Iacono, A. Lubiw, P. Morin, V. Sacristán, D. Souvaine, R. Uehara
Coverage with k-Transmitters in the Presence of Obstacles
Journal of Combinatorial Optimization, Vol. 25, N. 2, pp. 208-233, 2013. PDF
Preliminary version in Proc. 4th Annual International Conference on Combinatorial Optimization and Applications, LNCS 6509, pp.1-15, Hawaii, December 18-20, 2010. PDF


B. M. Ábrego, R. Fabila-Monroy, S. Fernández-Merchant, D. Flores-Peñaloza, F. Hurtado, H. Meijer, V. Sacristán, M. Saumell
Proximity Graphs inside Large Weighted Graphs
Networks, Vol. 61, N. 1, pp. 29-39,  2013. PDF
Preliminary version in Proc. 26th European Workshop on Computational Geometry (EuroCG’10), pp. 9-12, 2010. PDF


R. Chalmeta, F. Hurtado, V. Sacristán, M. Saumell
Measuring regularity of convex polygons
Computer-Aided Design, Vol. 45, pp. 93–104, 2013. PDF
Go to the regularity measures web page
Preliminary partial abstract: R. Chalmeta, V. Sacristán, M. Saumell, Measuring regularity of convex polygons: experimental results, Proc. XIV Spanish Meeting on Computational Geometry, Alcalá de Henares (Spain), June 27-30, pp. 71-74, 2011. PDF
Preliminary partial abstract: F. Hurtado, M. Saumell, V. Sacristán, Some regularity measures for convex polygons, Proc. 25th European Workshop in Computational Geometry, pp. 125-129, 2009. PDF (preliminary version in Proc. VI Jornadas de Matemática Discreta y Algorítmica, pp. 401-408, 2008 PDF).


P. Bose, S. Collette, F. Hurtado, M. Korman, S. Langerman, V. Sacristán, M. Saumell
Some properties of k-Delaunay and k-Gabriel graphs
Computational Geometry – Theory and Applications, Vol. 46, N. 2, pp. 131–139, 2013. PDF
Preliminary version: Some Properties of Higher order Delaunay and Gabriel Graphs, Proc. 22nd Canadian Conference on Computational Geometry (CCCG’10), pp. 13-16, 2010. PDF


M. Abellanas, M. Claverol, G. Hernández-Peñalver, F. Hurtado, V. Sacristán, M. Saumell, R. I. Silveira
Improving shortest paths in the Delaunay triangulation
International Journal of Computational Geometry and Applications, Vol. 22, N. 6, pp. 559-576, 2012. PDF
Preliminary version in Proc. 27th European Workshop on Computational Geometry, Morschach, Switzerland, March 28-30, pp. 43-46, 2011. PDF
Extended abstract in Proc. XIV Spanish Meeting on Computational Geometry, Alcalá de Henares, Spain, June 27-30, pp. 117-120, 2011. PDF


P. Bose, V. Dujmović, F. Hurtado, J. Iacono, S. Langerman, H. Meijer, V. Sacristán, M. Saumell, D. R. Wood
Proximity graphs: E, δ, Δ, χ and ω
International Journal of Computational Geometry and Applications, Vol. 22, N. 5, pp. 439–469, 2012. PDF
Preliminary version: Proc. 28th European Workshop in Computational Geometry, pp. 217-220, 2012. PDF


M. Buchin, A. Driemel, M. van Kreveld, V. Sacristán
Segmenting trajectories: A framework and algorithms using spatiotemporal criteria
Journal of Spatial Information Science, Vol. 3, pp. 33-63, 2011. PDF
Preliminary partial version: An Algorithmic Framework for Segmenting Trajectories based on Spatio-Temporal Criteria, Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 202-211, 2010. PDF


B. M. Ábrego, R. Fabila, S. Fernández, D. Flores, F. Hurtado, V. Sacristán, M. Saumell
On Crossing Numbers in Geometric Proximity Graphs
Computational Geometry – Theory and Applications, Vol. 44, N. 4, pp. 216.233, 2011. PDF
Preliminary version in Actas XIII Encuentros de Geometría Computacional, pp. 151-156, Zaragoza (España), 2009. PDF


G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman, J. O’Rourke, V. Pinciu, S. Ramaswami, V. Sacristán, S Wuhrer
Efficient Constant-Velocity Reconfiguration of Crystalline Robots
Robotica, Vol. 29, N. 1, pp. 59-71, 2011. PDF
Preliminary version: Realistic Reconfiguration of Crystalline (and Telecube) Robots, Proc. 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008), 2008. PDF


G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman, J. O’Rourke, S. Ramaswami, V. Sacristán, S. Wuhrer
Linear Reconfiguration of Cube-Style Modular Robots
Computational Geometry – Theory and Applications Vol. 42, N. 6-7, pp. 652–663, 2009. PDF
Preliminary version in Proc. 18th International Symposium on Algorithms and Computation (ISAAC2007), LNCS 4935, pp. 208-219, Springer-Verlag, 2007.PDF


M. Abellanas, G. Hernández, V. Sacristán
Caminos de desviación mínima local
Actas XIII Encuentros de Geometría Computacional, pp. 285-292, Zaragoza (España), 2009. PDF


M. Abellanas, G. Hernández, J. L. Moreno, S. Ordóñez, V. Sacristán
DVALon: una herramienta para diagramas de Voronoi y grafos de proximidad de alcance limitado
Actas XIII Encuentros de Geometría Computacional, pp. 293-300, Zaragoza (España), 2009. PDF


G. Aloupis, S. Collette, E. D. Demaine, S. Langerman, S. Ramaswami, V. Sacristán, S. Wuhrer
Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves
Proc. 19th International Symposium on Algorithms and Computation (ISAAC2008), LNCS 5369, pp. 342-353, Springer-Verlag, 2008. PDF


F.Hurtado, M.Noy, J.M.Robert, V.Sacristán and S.Skiena.
Visualizing Objects with Mirrors
Computer Graphics Forum, Vol. 23, Num. 2, pp. 157-166, 2004. PDF
Preliminary version in Technical Report 96-001, Computer Science Dept., State University of New York at Stony Brook, 1996. Spanish (partial) version in Actas del VI Congreso Español de Informática Gráfica, pp.51-65, 1996.


F. Hurtado, R. Klein, E. Langetepe, V. Sacristán.
The weighted farthest color Voronoi diagram on trees and graphs
Computational Geometry-Theory and Applications, Vol. 27, Num. 1, pp. 13-26, 2004. PDF
Extended abstract in Proc.18th European Conference on Computational Geometry, pp. 8-11, 2002.


E. Arkin, S. Fekete, F. Hurtado, J. Mitchell, M. Noy, V. Sacristán, S. Sethia.
On the Reflexivity of Point Sets
The Goodman-Pollack Festschrift, pp. 139-156, Springer-Verlag, 2003. Link
Preliminary version in Proc. 7th International Workshop on Algorithms and Data Structures, LNCS 2125, pp. 192-204, Springer-Verlag, 2001. PDF
Extended Abstract in Actas de los IX Encuentros de Geometría Computacional, pp. 239-249, 2001. Abstract in Proc. Tenth Annual Fall Workshop On Computational Geometry, Stony Brook, NY, October 2000.


D. Bremner, F. Hurtado, S. Ramaswami, and V. Sacristán.
Small Strictly Convex Quadrilateral Meshes of Point Sets
Algorithmica, Vol. 38, Num. 2, pp. 317-339, 2003. PDF
Preliminary version in Proc. Inte. Symp. on Algorithms and Computation 2001 (ISAAC), LNCS 2223, pp. 623-635, Springer-Verlag, 2001. PDF


M. Abellanas, F. Hurtado, C. Icking, E. Langetepe, R. Klein, L. Ma, B. Palop, V. Sacristán.
Voronoi Diagram for services neighboring a highway
Information Processing Letters, Vol. 86, Num. 5, pp. 283-288, 2003. PDF


O. Aichholzer, D. Bremner, E. Demaine, H. Meijer, V. Sacristán, M. Soss
Long Proteins with Unique Optimal Foldings in the H-P Model
Computational Geometry – Theory and Applications, Vol. 25, pp. 139-159, 2003. PDF
Extended Abstract in Proc. 17th European Workshop on Computational Geometry, pp. 59-62, 2001.


O. Devillers, R. Estkowski, P. M. Gandoin, F. Hurtado, P. Ramos, V. Sacristán
Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction
International Journal of Computational Geometry and Applications, Vol. 13, Num. 5, pp. 391-398, 2003. PDF
Preliminary version in Technical Report 4119, INRIA Sophia-Antipolis, 2000. Extended abstract (in spanish) in  Actas de los IX Encuentros de Geometría Computacional, pp. 167-174, 2001.


M. Abellanas, F. Hurtado, R. Klein, E. Langetepe, B. Palop, V. Sacristán.
Bichromatic 2-center problem
Actas de los X Encuentros de Geometría Computacional (in Spanish), pp. 131-137, Sevilla, 2003. PDF


P. Bose, F. Hurtado, H. Meijer, S. Ramaswami, D. Rappaport, V. Sacristán, T. Shermer and G. Toussaint.
Finding Specified Sections of Arrangements: 2D Results
In Journal of Mathematical Modeling and Algorithms, Vol. 1, Num. 1, pp. 3-16, 2002. PDF
Preliminary version in Proc. 10th Canadian Conference on Computational Geometry, pp. 20-21, 1998.


B. Chazelle, O. Devillers, F. Hurtado, M. Mora, V. Sacristán, M. Teillaud.
Splitting a Delaunay Triangulation in Linear Time
Algorithmica, Vol 34, Num. 1, pp. 39-46, 2002. PDF
Preliminary version in Proc. 9th Annual European Symposium on Algorithms, LNCS 2161, pp. 312-320, Springer-Verlag, 2001. PDF
Extended abstract in Actas de los IX Encuentros de Geometría Computacional (in Spanish), pp. 157-166, Girona, 2001.


F. Gómez, F. Hurtado, S. Ramaswami, V. Sacristán and G. Toussaint.
Implicit Convex Polygons
Journal of Mathematical Modelling and Algorithms, Vol. 1, Num. 1, pp. 57-85, 2002. PDF
Abstract in Proc. 14th European Workshop in Computational Geometry, pp. 83-86, 1998.


M. Abellanas, F. Hurtado, C. Ickling, R. Klein, E. Langetepe, L. MA, B. Palop, V. Sacristán.
Smallest Color-Spanning Objects
Proc. 9th Annual European Symposium on Algorithms, LNCS 2161, pp. 278-292, Springer-Verlag, 2001. PDF


M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop, V. Sacristán.
The Farthest-Color Voronoi Diagram and Related Problems
Extended abstract in Proc. 17th European Workshop on Computational Geometry, pp. 113-116, 2001.
Extended abstract (in spanish) in Actas de los IX Encuentros de Geometría Computacional, pp. 51-54, 2001.


M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop, V. Sacristán
Proximity Problems for Time Metrics Induced by the L1-Metric and Isothetic Networks
Extended abstract in Actas de los IX Encuentros de Geometría Computacional, pp. 175-182, 2001. PDF


F.Hurtado, V.Sacristán, G.Toussaint.
Some Constrained Minimax and Maximin Location Problems
Studies in Locational Analysis, 15, pp. 17-35, dec. 2000. PDF
Preliminary version in Proc. 10th Canadian Conference in Computational Geometry, pp. 24-25, 1998.


F. Hurtado, B. Palop, V. Sacristán.
Diagramas de Voronoi con funciones temporales
Actas de los VIII Encuentros de Geometría Computacional (in Spanish), pp. 279-287, 1999. PDF


E.Arkin, Y.J.Chiang, M. Held, J.Mitchell, V.Sacristán, S.Skiena, T.C. Yang.
On Minimum-Area Hulls
Algorithmica, Vol. 21, pp. 119-136, 1998. PDF
Preliminary version in Proc. 4th Annual European Symposium on Algorithms, LNCS 1136, pp. 334-348, 1996. Link


V. Sacristán.
Lower bounds for some geometric problems
Technical Report MA-IR-98-0034, Universitat Politècnica de Catalunya, Departament de Matemàtica Aplicada II, 1998. PDF
Abstract in Actas VIII Encuentros de Geometría Computacional, pp. 371-372, 1999.


F. Hurtado, V. Sacristán and G. Toussaint.
Pruning can solve from Facility Location to Visibility Problems
Proc. Journées Francoespagnoles de Géométrie Algoritmique, pp. 53-61, 1997. PDF


F. Hurtado, V. Sacristán and G. Toussaint.
Ángulo de apertura en la visión en dos y tres dimensiones
Actas VII Encuentros de Geometría Computacional, pp. 15-28, 1997. PDF


V. Sacristán.
Geometric Optimization and Applications in Visibility
My Phd. Thesis (in spanish) was supervised by Ferran Hurtado (1997).
Contents:
1. Introduction
2. Quality images
3. Visibility by reflection
4. Optimization with linear programming and median finding.
5. Optimization of the angle of aperture and vision through obstacles.
6. References
PDF


G. Blanco, J. García, F. Hurtado, P. Ramos and V. Sacristán.
Incidence angle constrained visibility
Proc. 12th European Workshop on Computational Geometry, pp. 27-28, 1996. PDF
Preliminary version (in spanish): Fotografías de Calidad, Actas VI Encuentros de Geometría Computacional, pp. 93-101, 1995.