Skip to main content

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Contribución de congreso (ConferenceOutput)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s,t) , which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s,t) , which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path SGPw(s,t) , which is a shortest path whose edges are edges of the tessellation. The ratios ¿SGPw(s,t)¿¿SPw(s,t)¿ , ¿SVPw(s,t)¿¿SPw(s,t)¿ , ¿SGPw(s,t)¿¿SVPw(s,t)¿ provide estimates on the quality of the approximation. Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that ¿SGPw(s,t)¿¿SPw(s,t)¿=23v˜1.15 in the worst case, and this is tight., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Colored Ray configurations

  • Fabila Monroy, Ruy
  • Garcia Olaverri, Alfredo Martin
  • Hurtado Díaz, Fernando Alfredo|||0000-0002-0108-9671
  • Jaume, Rafel
  • Pérez Lantero, Pablo
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Tejel Altarriba, Francisco Javier
  • Urrutia Galicia, Jorge
We study the cyclic sequences induced at in nity by pairwise-disjoint colored rays with apices on a given bal- anced bichromatic point set, where the color of a ray is inherited from the color of its apex. We derive a lower bound on the number of color sequences that can be realized from any xed point set. We also examine se- quences that can be realized regardless of the point set and exhibit negative examples as well. In addition, we provide algorithms to decide whether a sequence is re- alizable from a given point set on a line or in convex position, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

On maximum-sum matchings of points

  • Bereg, Sergey
  • Chacón Rivera, Oscar
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Huemer et al. (Discrete Math., 2019) proved that for any two point sets R and B with |R| = |B|, the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. In this work we study the perfect matching that maximizes the total Euclidean distance. First, we prove that this setting does not always ensure the common intersection property of the disks. Second, we extend the study for sets of 2n uncolored points. As the main result, we prove that in this case all disks of the matching do have a common point.
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Spanning ratio of shortest paths in weighted square tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path SPw(s, t), which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path SGPw(s, t), which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio kSGPw(s,t)k kSPw(s,t)k is at most v 2 2+v 2 ˜ 1.08, irrespective of the weight assignment., P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is funded by an FPU of the Universidad de Alcalá., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Farthest color Voronoi diagrams: complexity and algorithms

  • Mantas, Ioannis
  • Papadopoulou, Evanthia|||0000-0003-0144-7384
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
The farthest-color Voronoi diagram (FCVD) is a farthestsite Voronoi structure defined on a family P of m point-clusters in the plane, where the total number of points is n. The FCVD finds applications in problems related to color spanning objects and facility location. We identify structural properties of the FCVD, refine its combinatorial complexity bounds, and list conditions under which the diagram has O(n) complexity. We show that the diagram may have complexity ¿(n + m2 ) even if clusters have disjoint convex hulls. We present construction algorithms with running times ranging from O(n log n), when certain conditions are met, to O((n+s(P)) log3 n) in general, where s(P) is a parameter reflecting the number of straddles between pairs of clusters in P (s(P) ¿ O(mn)). A pair of points q1, q2 ¿ Q is said to straddle p1, p2 ¿ P if the line segment q1q2 intersects (straddles) the line through p1, p2 and the disks through (p1, p2, q1) and (p1, p2, q2) contain no points of P, Q. The complexity of the diagram is shown to be O(n + s(P))., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Some results on the laplacian spectra of Token graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Huemer, Clemens|||0000-0001-7557-0823
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_11. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use http://www.spingernature.com/gp/open-research/policies/accepted-manuscript-terms., We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this work, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1=h=k=n2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G) . Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G¯¯¯¯ . This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs., The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by PID2019-104129GBI00/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. F. J. Zaragoza Mart´ınez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Colored Ray configurations

  • Fabila Monroy, Ruy
  • Garcia Olaverri, Alfredo Martin
  • Hurtado Díaz, Fernando Alfredo
  • Jaume, Rafel
  • Pérez Lantero, Pablo
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio
  • Tejel Altarriba, Francisco Javier
  • Urrutia Galicia, Jorge
We study the cyclic sequences induced at in nity by pairwise-disjoint colored rays with apices on a given bal- anced bichromatic point set, where the color of a ray is inherited from the color of its apex. We derive a lower bound on the number of color sequences that can be realized from any xed point set. We also examine se- quences that can be realized regardless of the point set and exhibit negative examples as well. In addition, we provide algorithms to decide whether a sequence is re- alizable from a given point set on a line or in convex position, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Farthest color Voronoi diagrams: complexity and algorithms

  • Mantas, Ioannis
  • Papadopoulou, Evanthia
  • Sacristán Adinolfi, Vera
  • Silveira, Rodrigo Ignacio
The farthest-color Voronoi diagram (FCVD) is a farthestsite Voronoi structure defined on a family P of m point-clusters in the plane, where the total number of points is n. The FCVD finds applications in problems related to color spanning objects and facility location. We identify structural properties of the FCVD, refine its combinatorial complexity bounds, and list conditions under which the diagram has O(n) complexity. We show that the diagram may have complexity ¿(n + m2 ) even if clusters have disjoint convex hulls. We present construction algorithms with running times ranging from O(n log n), when certain conditions are met, to O((n+s(P)) log3 n) in general, where s(P) is a parameter reflecting the number of straddles between pairs of clusters in P (s(P) ¿ O(mn)). A pair of points q1, q2 ¿ Q is said to straddle p1, p2 ¿ P if the line segment q1q2 intersects (straddles) the line through p1, p2 and the disks through (p1, p2, q1) and (p1, p2, q2) contain no points of P, Q. The complexity of the diagram is shown to be O(n + s(P))., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Some results on the laplacian spectra of Token graphs

  • Dalfó Simó, Cristina
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel
  • Huemer, Clemens
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_11. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use http://www.spingernature.com/gp/open-research/policies/accepted-manuscript-terms., We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this work, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1=h=k=n2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G) . Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G¯¯¯¯ . This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs., The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by PID2019-104129GBI00/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. F. J. Zaragoza Mart´ınez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s,t) , which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s,t) , which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path SGPw(s,t) , which is a shortest path whose edges are edges of the tessellation. The ratios ¿SGPw(s,t)¿¿SPw(s,t)¿ , ¿SVPw(s,t)¿¿SPw(s,t)¿ , ¿SGPw(s,t)¿¿SVPw(s,t)¿ provide estimates on the quality of the approximation. Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that ¿SGPw(s,t)¿¿SPw(s,t)¿=23v˜1.15 in the worst case, and this is tight., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

On maximum-sum matchings of points

  • Bereg, Sergey
  • Chacón Rivera, Oscar
  • Flores Peñaloza, David
  • Huemer, Clemens
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
Huemer et al. (Discrete Math., 2019) proved that for any two point sets R and B with |R| = |B|, the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. In this work we study the perfect matching that maximizes the total Euclidean distance. First, we prove that this setting does not always ensure the common intersection property of the disks. Second, we extend the study for sets of 2n uncolored points. As the main result, we prove that in this case all disks of the matching do have a common point., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Spanning ratio of shortest paths in weighted square tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path SPw(s, t), which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path SGPw(s, t), which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio kSGPw(s,t)k kSPw(s,t)k is at most v 2 2+v 2 ˜ 1.08, irrespective of the weight assignment., P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is funded by an FPU of the Universidad de Alcalá., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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)