Pasar al contenido principal

GRAFOS Y GEOMETRIA: INTERACCIONES Y APLICACIONES

MTM2015-63791-R

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Dirección General de Investigación Científica y Técnica
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 20
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñazola, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Let S ¿ [0, 1]2 be a set of n points, randomly and uniformly selected. Let R ¿ B be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random number M(n) of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n) = 0.83 n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Computing optimal shortcuts for networks

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Rodríguez, Natalia
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Questions of this type have received considerable attention recently, mostly for discrete variants of the problem. We study a fully continuous setting, where all points on the network and the inserted segment must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model, together with several results for networks that are paths, restricted to two types of shortcuts: shortcuts with a fixed orientation and simple shortcuts., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Affine invariant triangulations

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set S for any (unknown) affine transformation of S. Our work is based on a method by Nielson [A characterization of an affine invariant triangulation. Geom. mod, 191-210. Springer, 1993] that uses the inverse of the covariance matrix of S to define an affine invariant norm, denoted AS, and an affine invariant triangulation, denoted DT AS [S]. We revisit the AS-norm from a geometric perspective, and show that DT AS [S] can be seen as a standard Delaunay triangulation of a transformed point set based on S. We prove that it retains all of its well-known properties. In addition, we provide different affine invariant order methods of a point set S and of the vertices of a polygon P that can be combined with well-known algorithms in order to obtain other affine invariant triangulation methods of S and P., ∗P.B. was partially supported by NSERC. P.C. was supported by CONACyT. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Computing optimal shortcuts for networks

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Rodríguez, Natalia
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We augment a plane Euclidean network with a segment or shortcut to minimize the largest distance between any two points along the edges of the resulting network. In this continuous setting, the problem of computing distances and placing a shortcut is much harder as all points on the network, instead of only the vertices, must be taken into account. Our main result for general networks states that it is always possible to determine in polynomial time whether the network has an optimal shortcut and compute one in case of existence. We also improve this general method for networks that are paths, restricted to using two types of shortcuts: those of any fixed direction and shortcuts that intersect the path only on its endpoints., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Pole Dancing: 3D Morphs for Tree Drawings

  • Arseneva, Elena
  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • D'Angelo, Anthony
  • Dujmovic, Vida
  • Frati, Fabrizio
  • Langerman, Stefan
  • Tappini, Alessandra
We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter T(n) steps are always sufficient and sometimes necessary.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Hamiltonicity for convex shape Delaunay and Gabriel Graphs

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DGC(S), has vertex set S, and edges defined as follows. Given p, q ¿ S, pq is an edge of k-DGC(S) provided there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph, denoted k-GGC(S), is defined analogously, except that the homothets considered are restricted to be smallest homothets of C with p and q on the boundary. We provide upper bounds on the minimum value of k for which k-GGC(S) is Hamiltonian. Since k-GGC(S) ¿ k-DGC(S), all results carry over to k-DGC(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve these bounds to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t = 10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. In addition, we show lower bounds of k = 3 and k = 6 on the existence of a bottleneck Hamiltonian cycle in the k-order Gabriel graph for squares and hexagons, respectively. Finally, we construct a point set such that for an infinite family of regular polygons Pt, the Delaunay graph DGPt does not contain a Hamiltonian cycle., ∗P.B. was partially supported by NSERC. P.C. was supported by CONACyT. M.S. was supported by the Czech Science Foundation, grant number GJ19-06792Y, and by institutional support RVO:67985807. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Pérez Lantero, Pablo
Let S[0,1]2 be a set of n points, randomly and uniformly selected. Let RB be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n)=0.83n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain., Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Sequences of spanning trees for L-infinity Delaunay triangulations

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We extend a known result about L2-Delaunay triangulations to L∞-Delaunay. Let TS be the set of all non-crossing spanning trees of a planar n-point set S. We prove that for each element T of TS, there exists a length-decreasing sequence of trees T0, . . . , Tk in the L∞-metric such that T0 = T, Tk = MST(S) and Ti does not cross Ti−1 for all i = 1, . . . , k, where MST(S) denotes the minimum spanning tree of S in the L∞ metric. We also give an Ω(log n) lower bound for the length of the sequence, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity

  • Fabila Monroy, Ruy
  • Hidalgo Toscano, Carlos
  • Huemer, Clemens|||0000-0001-7557-0823
  • Lara, Dolores
  • Mitsche, Dieter
This is a post-peer-review, pre-copyedit version of an article published in International Symposium on Graph Drawing and Network Visualization. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-04414-5_42, How to draw the vertices of a complete multipartite graph G on different points of a bounded d-dimensional integer grid, such that the sum of squared distances between vertices of G is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case d = 1, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Flips in higher order Delaunay triangulations

  • Arseneva, Elena
  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-61792-9_18, We study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S. The flip graph of S has one vertex for each possible triangulation of S, and an edge connecting two vertices when the two corresponding triangulations can be transformed into each other by a flip (i.e., exchanging the diagonal of a convex quadrilateral by the other one). The flip graph is an essential structure in the study of triangulations, but until now it had been barely studied for order-k Delaunay triangulations. In this work we show that, even though the order-k flip graph might be disconnected for k = 3, any order-k triangulation can be transformed into some other order-k triangulation by at most k - 1 flips, such that the intermediate triangulations are of order at most 2k - 2, in the following settings: (1) for any k = 0 when S is in convex position, and (2) for any k = 5 and any point set S. Our results imply that the flip distance between two order-k triangulations is O(kn), as well as an efficient enumeration algorithm., E.A. was supported by RFBR, project number 20-01-00488. P.B. was partially supported by NSERC. P.C. was supported by CONACYT, MX. R.S. was supported by MINECO through the Ramón y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñazola, David
  • Huemer, Clemens
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
Let S ¿ [0, 1]2 be a set of n points, randomly and uniformly selected. Let R ¿ B be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random number M(n) of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n) = 0.83 n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Affine invariant triangulations

  • Bose, Prosenjit
  • Cano Vila, María del Pilar
  • Silveira, Rodrigo Ignacio
We study affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set S for any (unknown) affine transformation of S. Our work is based on a method by Nielson [A characterization of an affine invariant triangulation. Geom. mod, 191-210. Springer, 1993] that uses the inverse of the covariance matrix of S to define an affine invariant norm, denoted AS, and an affine invariant triangulation, denoted DT AS [S]. We revisit the AS-norm from a geometric perspective, and show that DT AS [S] can be seen as a standard Delaunay triangulation of a transformed point set based on S. We prove that it retains all of its well-known properties. In addition, we provide different affine invariant order methods of a point set S and of the vertices of a polygon P that can be combined with well-known algorithms in order to obtain other affine invariant triangulation methods of S and P., ∗P.B. was partially supported by NSERC. P.C. was supported by CONACyT. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Flips in higher order Delaunay triangulations

  • Arseneva, Elena
  • Bose, Prosenjit
  • Cano Vila, María del Pilar
  • Silveira, Rodrigo Ignacio
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-61792-9_18, We study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S. The flip graph of S has one vertex for each possible triangulation of S, and an edge connecting two vertices when the two corresponding triangulations can be transformed into each other by a flip (i.e., exchanging the diagonal of a convex quadrilateral by the other one). The flip graph is an essential structure in the study of triangulations, but until now it had been barely studied for order-k Delaunay triangulations. In this work we show that, even though the order-k flip graph might be disconnected for k = 3, any order-k triangulation can be transformed into some other order-k triangulation by at most k - 1 flips, such that the intermediate triangulations are of order at most 2k - 2, in the following settings: (1) for any k = 0 when S is in convex position, and (2) for any k = 5 and any point set S. Our results imply that the flip distance between two order-k triangulations is O(kn), as well as an efficient enumeration algorithm., E.A. was supported by RFBR, project number 20-01-00488. P.B. was partially supported by NSERC. P.C. was supported by CONACYT, MX. R.S. was supported by MINECO through the Ramón y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Hamiltonicity for convex shape Delaunay and Gabriel Graphs

  • Bose, Prosenjit
  • Cano Vila, María del Pilar
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DGC(S), has vertex set S, and edges defined as follows. Given p, q ¿ S, pq is an edge of k-DGC(S) provided there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph, denoted k-GGC(S), is defined analogously, except that the homothets considered are restricted to be smallest homothets of C with p and q on the boundary. We provide upper bounds on the minimum value of k for which k-GGC(S) is Hamiltonian. Since k-GGC(S) ¿ k-DGC(S), all results carry over to k-DGC(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve these bounds to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t = 10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. In addition, we show lower bounds of k = 3 and k = 6 on the existence of a bottleneck Hamiltonian cycle in the k-order Gabriel graph for squares and hexagons, respectively. Finally, we construct a point set such that for an infinite family of regular polygons Pt, the Delaunay graph DGPt does not contain a Hamiltonian cycle., ∗P.B. was partially supported by NSERC. P.C. was supported by CONACyT. M.S. was supported by the Czech Science Foundation, grant number GJ19-06792Y, and by institutional support RVO:67985807. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Sequences of spanning trees for L-infinity Delaunay triangulations

  • Bose, Prosenjit
  • Cano Vila, María del Pilar
  • Silveira, Rodrigo Ignacio
We extend a known result about L2-Delaunay triangulations to L∞-Delaunay. Let TS be the set of all non-crossing spanning trees of a planar n-point set S. We prove that for each element T of TS, there exists a length-decreasing sequence of trees T0, . . . , Tk in the L∞-metric such that T0 = T, Tk = MST(S) and Ti does not cross Ti−1 for all i = 1, . . . , k, where MST(S) denotes the minimum spanning tree of S in the L∞ metric. We also give an Ω(log n) lower bound for the length of the sequence, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Computing optimal shortcuts for networks

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Rodríguez, Natalia
  • Silveira, Rodrigo Ignacio
We augment a plane Euclidean network with a segment or shortcut to minimize the largest distance between any two points along the edges of the resulting network. In this continuous setting, the problem of computing distances and placing a shortcut is much harder as all points on the network, instead of only the vertices, must be taken into account. Our main result for general networks states that it is always possible to determine in polynomial time whether the network has an optimal shortcut and compute one in case of existence. We also improve this general method for networks that are paths, restricted to using two types of shortcuts: those of any fixed direction and shortcuts that intersect the path only on its endpoints., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Pole Dancing: 3D Morphs for Tree Drawings

  • Arseneva, Elena
  • Bose, Prosenjit
  • Cano Vila, María del Pilar
  • D'Angelo, Anthony
  • Dujmovic, Vida
  • Frati, Fabrizio
  • Langerman, Stefan
  • Tappini, Alessandra
We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter T(n) steps are always sufficient and sometimes necessary., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity

  • Fabila Monroy, Ruy
  • Hidalgo Toscano, Carlos
  • Huemer, Clemens
  • Lara, Dolores
  • Mitsche, Dieter
This is a post-peer-review, pre-copyedit version of an article published in International Symposium on Graph Drawing and Network Visualization. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-04414-5_42, How to draw the vertices of a complete multipartite graph G on different points of a bounded d-dimensional integer grid, such that the sum of squared distances between vertices of G is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case d = 1, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñaloza, David
  • Huemer, Clemens
  • Seara Ojea, Carlos
  • Pérez Lantero, Pablo
Let S[0,1]2 be a set of n points, randomly and uniformly selected. Let RB be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n)=0.83n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain., Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Computing optimal shortcuts for networks

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Rodríguez, Natalia
  • Silveira, Rodrigo Ignacio
We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Questions of this type have received considerable attention recently, mostly for discrete variants of the problem. We study a fully continuous setting, where all points on the network and the inserted segment must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model, together with several results for networks that are paths, restricted to two types of shortcuts: shortcuts with a fixed orientation and simple shortcuts., Peer Reviewed, Postprint (published version)