Graphic summary
  • Show / hide key
  • Information


Scientific and technological production
  •  

1 to 50 of 136 results
  • Evaluación de la investigación: el declive de un modelo exitoso / Evaluating research: the decline of a successful model

     Sacristán Adinolfi, Vera
    RES. Revista Española de Sociología
    Vol. 21, p. 149-156
    Date of publication: 2014
    Journal article

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

  • Coverage with k-transmitters in the presence of obstacles

     Ballinger, Brad; Benbernou, Nadia; Bose, Prosenjit; Damian, Mirela; Demaine, Erik D.; Dujmovic, Vida; Flatland, Robin; Hurtado Diaz, Fernando Alfredo; Iacono, John; Lubiw, Anna; Morin, Pat; Sacristán Adinolfi, Vera; Souvaine, Diane; Uehara, Ryuhei
    Journal of combinatorial optimization
    Vol. 25, num. 2, p. 208-233
    DOI: 10.1007/s10878-012-9475-x
    Date of publication: 2013-02
    Journal article

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

    For a fixed integer ka parts per thousand yen0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k "walls", represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

  • Some properties of k-Delaunay and k-Gabriel graphs

     Bose, Prosenjit; Collette, Sébastien; Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Langerman, Stefan; Sacristán Adinolfi, Vera; Saumell, Maria
    Computational geometry: theory and applications
    Vol. 46, num. 2, p. 131-139
    DOI: 10.1016/j.comgeo.2012.04.006
    Date of publication: 2013-02
    Journal article

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

    We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, connectivity, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.

  • Measuring regularity of convex polygons

     Chalmeta Ugas, Ramon; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Masalles Saumell, Ramon Maria
    Computer Aided Design
    Vol. 45, num. 2, p. 93-104
    DOI: 10.1016/j.cad.2012.07.012
    Date of publication: 2013-02
    Journal article

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

    We propose several measures to evaluate to which extent the shape of a given convex polygon is close to be regular, focusing on a range of characteristics of regularity: optimal ratio area¿perimeter, equality of angles and edge lengths, regular fitting, angular and areal symmetry. We prove that our measures satisfy a number of reasonable requirements that guarantee them to be well defined, and provide efficient algorithms for their computation. All these algorithms have been implemented, and we provide experimental results on all the proposed measures.

  • Proximity graphs inside large weighted graphs

     Ábrego, Bernardo M.; Fabila Monroy, Ruy; Fernández Merchant, Silvia; Flores Peñaloza, David; Hurtado Diaz, Fernando Alfredo; Meijer, Henk G. E.; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Networks
    Vol. 61, num. 1, p. 29-39
    DOI: 10.1002/net.21464
    Date of publication: 2013-01
    Journal article

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

    Given a weighted graph G = (V,E) and a subset U of V, we define several graphs with vertex set U in which two vertices are adjacent if they satisfy a specific proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation.

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

  • Empty triangles in good drawings of the complete graph

     Aichholzer, Oswin; Hackl, Thomas; Pilz, Alexander; Ramos Alonso, Pedro Antonio; Sacristán Adinolfi, Vera; Vogtenhuber, Birgit
    Mexican Conference on Discrete Mathematics and Computational Geometry
    p. 21-29
    Presentation's date: 2013
    Presentation of work at congresses

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

  • Simulating distributed algorithms for lattice agents

     Aichholzer, Oswin; Hackl, Thomas; Sacristán Adinolfi, Vera; Vogtenhuber, Birgit; Wallner, Reinhard
    Spanish Meeting on Computational Geometry
    p. 81-84
    Presentation's date: 2013-06-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

    We present a practical Java to ol for simulating syn- chronized distributed algorithms on sets of 2- and 3- dimensional square/cubic lattice-based agents. This AgentSystem assumes that each agent is capable to change p osition in the lattice and that neighb oring agents can attach and detach from each other. In addition, it assumes that each mo dule has some con- stant size memory and computation capability, and can send/receive constant size messages to/from its neighb ors. The system allows the user to dene sets of agents and sets of rules and apply one to the other. The AgentSystem simulates the synchronized execu- tion of the set of rules by all the mo dules, and can keep track of all actions made by the mo dules at each step, supp orting consistency warnings and error checking. Our intention is to provide a useful to ol for the re- searchers from geometric distributed algorithms.

  • Distributed universal reconfiguration of 2D lattice-based modular robots

     Hurtado Diaz, Fernando Alfredo; Molina Sarazá, Enrique; Ramaswami, Suneeta; Sacristán Adinolfi, Vera
    European Workshop on Computational Geometry
    p. 139-143
    Presentation's date: 2013
    Presentation of work at congresses

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

  • Quant paga l'estudiant?

     Arcas Abella, Oriol; Botella, J.; Corominas Subias, Albert; de la Villa, L.; França, J.; Sacristán Adinolfi, Vera
    Date of publication: 2012
    Book

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

  • Estudiar a Europa

     Tello, E.
    Date of publication: 2012
    Book

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

  • Proximity graphs: E, $\delta$, $\Delta$, $\Chi$ and $\omega$

     Bose, Prosenjit; Dumovic, V.; Hurtado Diaz, Fernando Alfredo; Iacono, John; Langerman, Stefan; Meijer, H; Sacristán Adinolfi, Vera; Saumell, Maria; Wood, David R.
    International journal of computational geometry and applications
    Vol. 22, num. 5, p. 439-469
    DOI: 10.1142/S0218195912500112
    Date of publication: 2012
    Journal article

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

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

  • Proximity graphs: E, d, D, X.

     Bose, Prosenjit; Dujmovic, Vida; Hurtado Diaz, Fernando Alfredo; Iacono, John; Langerman, Stefan; Meijer, H.; Sacristán Adinolfi, Vera; Saumell, Maria; Wood, D. R.
    European Workshop on Computational Geometry
    p. 217-220
    Presentation's date: 2012-03-20
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Some problems on proximity graphs

     Saumell Mendiola, Maria
    Department of Applied Mathematics II, Universitat Politècnica de Catalunya
    Theses

     Share Reference managers Reference managers Open in new window

  • 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

  • Competencias y competición: dos formas de la desregulación de la enseñanza en Europa (traducción)

     Sacristán Adinolfi, Vera
    Sin permiso: república y socialismo, también para el siglo XXI
    Date of publication: 2011-05-08
    Journal article

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

  • Las Encrucijadas estratégicas de la universidad pública española

     Corominas Subias, Albert; Sacristán Adinolfi, Vera
    Revista de educación
    Vol. 355, p. 57-81
    Date of publication: 2011-05
    Journal article

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

  • Access to the full text
    Segmenting trajectories: A framework and algorithms using spatiotemporal criteria  Open access

     Buchin, Maike; Driemel, Anne; Kreveld, Marc van; Sacristán Adinolfi, Vera
    Journal of Spatial Information Science
    Vol. 3, p. 33-63
    DOI: 10.5311/JOSIS.2011.3.66
    Date of publication: 2011
    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 address the problem of segmenting a trajectory based on spatiotemporal criteria. We require that each segment is homogeneous in the sense that a set of spatiotemporal criteria are fulfilled. We define different such criteria, including location, heading, speed, velocity, curvature, sinuosity, curviness, and shape. We present an algorithmic framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, a segmentation can generally be computed in O(n log n) time, where n is the number of edges of the trajectory to be segmented. We also discuss the robustness of our approach.

  • Access to the full text
    Efficient constant-velocity reconfiguration of crystalline robots  Open access

     Aloupis, Greg; Collette, Sébastien; Damian, M.; Demaine, Erik D.; El-Khechen, Dania; Flatland, R.; Langerman, Stefan; O'Rourke, J.; Pinciu, V.; Ramaswami, S.; Sacristán Adinolfi, Vera; Wuhrer, S.
    Robotica
    Vol. 29, num. 1, p. 59-71
    DOI: 10.1017/S026357471000072X
    Date of publication: 2011
    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 propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2x2x2 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration. Our algorithms involve a total of O(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous recon guration algorithms, which either use O(n2) parallel steps [Rus and Vona, 2001, Vassilvitskii et al., 2002, Butler and Rus, 2003] or do not respect the constraints men- tioned above [Aloupis et al., 2009b]. In fact, in the setting considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication.

  • On crossing numbers of geometric proximity graphs

     Ábrego, Bernardo M.; Fabila Monroy, Ruy; Fernández-Merchant, Silvia; Flores-Peñaloza, David; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Computational geometry: theory and applications
    Vol. 44, num. 4, p. 216-233
    DOI: 10.1016/j.comgeo.2010.11.003
    Date of publication: 2011-05
    Journal article

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

  • Measuring regularity of convex polygons: experimental results

     Chalmeta Ugas, Ramon; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Spanish Meeting on Computational Geometry
    p. 71-74
    Presentation's date: 2011-06-27
    Presentation of work at congresses

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

  • Generic distributed actuation of lattice-based modular robotic systems

     Sacristán Adinolfi, Vera
    Spanish Meeting on Computational Geometry
    p. 3-6
    Presentation's date: 2011-06-27
    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

  • 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

  • Sobre el gobierno de las universidades públicas

     Corominas Subias, Albert; Fillet Castella, Sergi; Ras Sabido, Antoni; Sacristán Adinolfi, Vera
    Date of publication: 2010
    Book chapter

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

  • PROBLEMAS DE COMBINATORIA Y DE COMPUTACION

     Claverol Aguas, Merce; Hernando Martin, Maria Del Carmen; Montes Lozano, Antonio; Mora Gine, Mercè; Sacristán Adinolfi, Vera; Seara Ojea, Carlos; Trias Pairo, Juan; Huemer, Clemens; Pfeifle, Julian Thoralf; Saumell Mendiola, Maria; Garcia Olaverri, Alfredo Martin; Tejel Altarriba, Francisco Javier; Dall, Aaron Matthew; Hurtado Diaz, Fernando Alfredo
    Competitive project

     Share

  • An algorithmic framework for segmenting trajectories based on spatio-temporal criteria

     Buchin, Maike; Driemel, Anne; Kreveld, Marc van; Sacristán Adinolfi, Vera
    ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
    p. 202-211
    DOI: 10.1145/1869790.1869821
    Presentation's date: 2010-11-02
    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

    In this paper we address the problem of segmenting a trajectory such that each segment is in some sense homogeneous. We formally define different spatio-temporal criteria under which a trajectory can be homogeneous, including location, heading, speed, velocity, curvature, sinuosity, and curviness. We present a framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, the segmentation problem can generally be solved in O(n log n) time, where n is the number of edges of the trajectory to be segmented.

  • Access to the full text
    Some properties of higher order delaunay and gabriel graphs  Open access

     Bose, Prosenjit; Collette, Sébastien; Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Langerman, Stefan; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Canadian Conference on Computational Geometry
    p. 13-16
    Presentation's date: 2010-08-09
    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 consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.

  • Coverage with k-transmitters in the presence of obstacles

     Ballinger, Brad; Benbernou, Nadia; Bose, Prosenjit; Damian, Mirela; Demaine, Erik D.; Dujmovic, Vida; Flatland, Robin; Hurtado Diaz, Fernando Alfredo; Iacono, John; Lubiw, Anna; Morin, Pat; Sacristán Adinolfi, Vera; Souvaine, Diane; Uehara, Ryuhei
    Annual International Conference on Combinatorial Optimization and Applications
    p. 1-15
    DOI: 10.1007/978-3-642-17461-2
    Presentation's date: 2010-12-18
    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

    For a fixed integer k ≥ 0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k “walls”, represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

  • Access to the full text
    Proximity graphs inside large weighted graphs  Open access

     Ábrego, Bernardo M.; Fabila Monroy, Ruy; Fernández-Merchant, Silvia; Flores Peñazola, David; Hurtado Diaz, Fernando Alfredo; MEIJER, HENK; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    European Workshop on Computational Geometry
    p. 9-12
    Presentation's date: 2010-03-24
    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

    Given a large weighted graph G = (V;E) and a subset U of V , we de¯ne several graphs with vertex set U in which two vertices are adjacent if they satisfy some prescribed proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the de¯ned graphs and provide algorithms for their computation.

  • El finançament de la universitat

     Sacristán Adinolfi, Vera
    Quina universitat pública volem?
    Presentation's date: 2009-05-16
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Access to the full text
    DVALon: una herramienta para diagramas de Voronoi y grafos de proximidad de alcance limitado  Open access

     Abellanas, Manuel; Hernández, Gregorio; Moreno, José Luis; Ordóñez, Sergio; Sacristán Adinolfi, Vera
    Encuentros de Geometría Computacional
    p. 293-300
    Presentation's date: 2009-07-01
    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

    Presentamos un estudio de los diagramas de Voronoi de alcance limitado de un conjunto finito de puntos del plano y DVALon, una herramienta para la manipulaci´on de dichos diagramas, los grafos de proximidad de alcance limitado y su aplicación a los caminos de desviación mínima y de separación máxima.

  • Sobre el gobierno de las universidades públicas

     Corominas Subias, Albert; Fillet Castella, Sergi; Ras Sabido, Antoni; Sacristán Adinolfi, Vera
    Construir el futuro de la universidad pública
    Presentation's date: 2009-06-01
    Presentation of work at congresses

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

  • Linear reconfiguration of cube-style modular robots

     Aloupis, Greg; Collette, Sébastien; Damian, M; Demaine, Erik D.; Flatland, R; Langerman, Stefan; O'Rourke, J; Ramaswami, S; Sacristán Adinolfi, Vera; Wuhrer, S
    Computational geometry: theory and applications
    Vol. 42, num. 6-7, p. 652-663
    Date of publication: 2009-08
    Journal article

     Share Reference managers Reference managers Open in new window

  • Access to the full text
    Caminos de desviación mínima local  Open access

     Hernández, Gregorio; Sacristán Adinolfi, Vera; Abellanas, Manuel
    Encuentros de Geometría Computacional
    p. 285-292
    Presentation's date: 2009-07-01
    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

    Un camino que conecta dos puntos s y t en el plano es de desviación mínima respecto de un conjunto de puntos S si la mayor de las distancias entre un punto del camino y S es la menor posible entre todos los caminos que conectan s y t. En este trabajo estudiamos los caminos de desviación mínima que satisfacen además que todo subcamino es también de desviación mínima, a los que llamamos caminos de desviación mínima local.

  • On Crossings in Geometric Proximity Graphs

     Bernardo, M Ábrego; Fabila Monroy, Ruy; Fernández-Merchant, Silvia; Flores-Peñaloza, David; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Encuentros de Geometría Computacional
    p. 151-156
    Presentation's date: 2009-06-30
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Some Regularity Measures for Convex Polygons

     Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    European Workshop on Computational Geometry
    p. 125-128
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Computational geometry: theory and applications

     Sacristán Adinolfi, Vera
    Collaboration in journals

     Share

  • Laboratori de Geometria per a Multimèdia

     Trias Pairo, Juan; Sacristán Adinolfi, Vera
    Date of publication: 2008-09
    Book chapter

     Share Reference managers Reference managers Open in new window

  • Access to the full text
    Realistic reconfiguration of crystalline (and telecube) robots  Open access

     Aloupis, Greg; Collette, Sébastien; Damian, Mirela; Demaine, Erik D.; El-Khechen, Dania; Flatland, Robin; Langerman, Stefan; O'Rourke, Joseph; Pinciu, Val; Ramaswami, Suneeta; Sacristán Adinolfi, Vera; Wuhrer, Stefanie
    International Workshop on the Algorithmic Foundations of Robotics
    p. 433-447
    Presentation's date: 2008-12
    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

    In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 x 2 x 2 modules. We respect certain physical constraints: each atom reaches at most unit velocity and (via expansion) can displace at most one other atom. We require that one of the atoms can store a map of the target con guration. Our algorithms involve a total of O(n²) such atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n²) parallel steps [7, 9, 4] or do not respect the constraints mentioned above [1]. In fact, in the setting considered, our algorithms are optimal, in the sense that certain reconfigurations require Ω(n) parallel steps. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configurations.

  • Reconfiguration of cube-style modular robots using O(logn) parallel moves

     Aloupis, Greg; Collette, Sébastien; Demaine, Erik D.; Langerman, Stefan; Sacristán Adinolfi, Vera; Wuhrer, Stefanie
    International Symposium on Algorithms and Computation
    p. 342-353
    DOI: 10.1007/978-3-540-92182-0_32
    Presentation's date: 2008
    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 model of reconfigurable robot, introduced and prototyped by the robotics community. The robot consists of independently manipulable unit-square atoms that can extend/contract arms on each side and attach/detach from neighbors. The optimal worst-case number of sequential moves required to transform one connected configuration to another was shown to be Θ(n) at ISAAC 2007. However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(log n) parallel steps, although the total number of operations increases slightly to Θ(n log n). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.

  • Opurtunitats i perills en la implantació de l'EEES

     Sacristán Adinolfi, Vera
    Debat sobre l'Espai Europeu d'Ensenyament Superior
    Presentation's date: 2008-12-15
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Some Regularity Measures for Convex Polygons

     Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Jornadas de Matemática Discreta y Algorítmica
    p. 401-408
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Linear Reconfiguration of Cube-Style Modular Robots

     Sacristán Adinolfi, Vera
    International Symposium on Algorithms and Computation
    p. 208-219
    Presentation's date: 2007-12-17
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Linear Reconfiguration of Cube-Style Modular Robots

     Aloupis, Greg; Collette, Sébastien; Damian, Mirela; Demaine, Erik D.; Flatland, Robin; Langerman, Stefan; O'Rourke, Joseph; Sacristán Adinolfi, Vera; Ramaswami, Suneeta; Wuhrer, Stefanie
    Encuentros de Geometría Computacional
    p. 19-26
    Presentation's date: 2007-06-25
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • METODOS ALGORITMICOS Y ESTRUCTURAS COMBINATORIAS EN GEOMETRIA COMPUTACIONAL

     Hurtado Diaz, Fernando Alfredo; Hernando Martin, Maria Del Carmen; Montes Lozano, Antonio; Sacristán Adinolfi, Vera; Mora Gine, Mercè
    Competitive project

     Share

  • Grupo de investigación consolidado de la Generalitat de Catalunya

     Hernando Martin, Maria Del Carmen; Hurtado Diaz, Fernando Alfredo; Montes Lozano, Antonio; Trias Pairo, Juan; Sacristán Adinolfi, Vera; Mora Gine, Mercè
    Competitive project

     Share

  • Combinatoria y computación en geometría discreta

     Hurtado Diaz, Fernando Alfredo; Hernando Martin, Maria Del Carmen; Sacristán Adinolfi, Vera; Mora Gine, Mercè
    Competitive project

     Share