Skip to main content

GRAFOS Y GEOMETRIA: INTERACCIONES Y APLICACIONES

MTM2015-63791-R

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2015
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Dirección General de Investigación Científica y Técnica
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 67
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 Artículo científico (JournalArticle)

A new lower bound on the maximum number of plane graphs using production matrices

  • Huemer, Clemens|||0000-0001-7557-0823
  • Pilz, Alexander
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We use the concept of production matrices to show that there exist sets of n points in the plane that admit ¿(42.11n ) crossing-free geometric graphs. This improves the previously best known bound of ¿(41.18n ) by Aichholzer et al. (2007).
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Artículo científico (JournalArticle)

Map construction algorithms: a local evaluation through hiking data

  • Duran, David
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
The final publication is available at Springer via http://dx.doi.org/10.1007/s10707-019-00386-7, We study five existing map construction algorithms, designed and tested with urban vehicle data in mind, and apply them to hiking trajectories with different terrain characteristics. Our main goal is to better understand the existing strategies and their limitations, in order to shed new light into the current challenges for map construction algorithms. We carefully analyze the results obtained by each algorithm focusing on the local details of the generated maps. Our analysis includes the characterization of 10 types of common artifacts, which occur in the results of more than one algorithm, and 7 algorithmic-specific artifacts, which are consequences of different algorithmic strategies. This allows us to extract systematic conclusions about the main challenges to fully automatize the construction of maps from trajectory data, to detect the strengths and weaknesses of the potential different strategies, and to suggest possible ways to design higher-quality map construction methods. We consider that this analysis will be of help for designing new and better methods that perform well in wider and more realistic contexts, not only for road map or hiking reconstruction, but also for other types of trajectory data., Departament de Matem`atiques, Universitat Polit`ecnica de Catalunya, and BGSMath, Spain. {vera.sacristan,rodrigo.silveira}@upc.edu. Partially supported by projects MTM2015-63791-R (MINECO/FEDER), Gen. Cat. 2017SGR1640. R.I. S. was also supported by MINECO through the Ram´on y Cajal program., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Capturing points with a rotating polygon (and a 3D extension)

  • Alegría Galicia, Carlos
  • Orden, David
  • Palios, Leonidas
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
This is a post-peer-review, pre-copyedit version of an article published in Theory of computing systems: an international journal. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00224-018-9885-y, We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a segment or a line. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A comparative analysis of trajectory similarity measures

  • Tao, Yaguang
  • Both, Alan
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Sijben, Stef
  • Buchin, Kevin
  • Purves, Ross S.
  • Laube, Patrick
  • Peng, Dongliang
  • Toohey, Kevin
  • Duckham, Matt
Computing trajectory similarity is a fundamental operation in movement analytics, required in search, clustering, and classification of trajectories, for example. Yet the range of different but interrelated trajectory similarity measures can be bewildering for researchers and practitioners alike. This paper describes a systematic comparison and methodical exploration of trajectory similarity measures. Specifically, this paper compares five of the most important and commonly used similarity measures: dynamic time warping (DTW), edit distance (EDR), longest common subsequence (LCSS), discrete Fréchet distance (DFD), and Fréchet distance (FD). The paper begins with a thorough conceptual and theoretical comparison. This comparison highlights the similarities and differences between measures in connection with six different characteristics, including their handling of a relative versus absolute time and space, tolerance to outliers, and computational efficiency. The paper further reports on an empirical evaluation of similarity in trajectories with contrasting properties: data about constrained bus movements in a transportation network, and the unconstrained movements of wading birds in a coastal environment. A set of four experiments: a. creates a measurement baseline by comparing similarity measures to a single trajectory subjected to various transformations; b. explores the behavior of similarity measures on network-constrained bus trajectories, grouped based on spatial and on temporal similarity; c. assesses similarity with respect to known behavioral annotations (flight and foraging of oystercatchers); and d. compares bird and bus activity to examine whether they are distinguishable based solely on their movement patterns. The results show that in all instances both the absolute value and the ordering of similarity may be sensitive to the choice of measure. In general, all measures were more able to distinguish spatial differences in trajectories than temporal differences. The paper concludes with a high-level summary of advice and recommendations for selecting and using trajectory similarity measures in practice, with conclusions spanning our three complementary perspectives: conceptual, theoretical, and empirical., This work was supported by the Ministry of Economy and Competitiveness (MINECO) [MTM2015-63791-R]; CRC for Spatial Information [Rapid Spatial Analytics]., 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 Artículo científico (JournalArticle)

A note on flips in diagonal rectangulations

  • Cardinal, Jean
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
Rectangulations are partitions of a square into axis-aligned rectangles. A number of results provide bijections between combinatorial equivalence classes of rectangulations and families of pattern-avoiding permutations. Other results deal with local changes involving a single edge of a rectangulation, referred to as flips, edge rotations, or edge pivoting. Such operations induce a graph on equivalence classes of rectangulations, related to so-called flip graphs on triangulations and other families of geometric partitions. In this note, we consider a family of flip operations on the equivalence classes of diagonal rectangulations, and their interpretation as transpositions in the associated Baxter permutations, avoiding the vincular patterns { 3{14}2, 2{41}3 }. This complements results from Law and Reading (JCTA, 2012) and provides a complete characterization of flip operations on diagonal rectangulations, in both geometric and combinatorial terms., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14]., A. Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR); M. Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT; and C. Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Convex quadrangulations of bichromatic point sets

  • Pilz, Alexander
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Electronic version of an article published as International journal of computational geometry and applications, 5 May 2020, vol. 29, núm. 4, p. 289-299. Article DOI 10.1142/S0218195919500109 © 2020 copyright World Scientific Publishing Company. Journal URL: https://www.worldscientific.com/doi/abs/10.1142/S0218195919500109, We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set S of points with each point either red or blue, does there exist a convex quadrangulation of S in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets., 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)

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
Publication Artículo científico (JournalArticle)

Non-crossing paths with geographic constraints

  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Speckmann, Bettina
  • Verbeek, Kevin
A geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geographic networks: can a given geographic network be drawn without crossings? We focus on the seemingly simple setting where each region is a unit length vertical segment, and one wants to connect pairs of segments with a path that lies inside the convex hull of the two segments. We prove that when paths must be drawn as straight line segments, it is NP-complete to determine if a crossing-free solution exists. In contrast, we show that when paths must be monotone curves, the question can be answered in polynomial time. In the more general case of paths that can have any shape, we show that the problem is polynomial under certain assumptions., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9–14].
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

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
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, 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 \(\mathcal {C}\) . Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- \({DG}_{\mathcal {C}}(S)\) , has vertex set S and edge pq provided that there exists some homothet of \(\mathcal {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 k- \({GG}_{\mathcal {C}}(S)\) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of \(\mathcal {C}\) with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- \({GG}_{\mathcal {C}}(S)\) is Hamiltonian. Since k- \({GG}_{\mathcal {C}}(S)\) \(\subseteq \) k- \({DG}_{\mathcal {C}}(S)\) , all results carry over to k- \({DG}_{\mathcal {C}}(S)\) . In particular, we give upper bounds of 24 for every \(\mathcal {C}\) and 15 for every point-symmetric \(\mathcal {C}\) . We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for \(t \ge 10)\) . These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs., 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 Artículo científico (JournalArticle)

K-1,K-3-covering red and blue points in the plane

  • Ábrego, Bernardo M.
  • Fernández Merchant, Silvia
  • Kano, Mikio
  • Orden, David
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tejel Altarriba, Francisco Javier
We say that a finite set of red and blue points in the plane in general position can be K1,3-covered if the set can be partitioned into subsets of size 4, with 3 points of one color and 1 point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set R of r red points and a set B of b blue points in the plane in general position, how many points of R ¿ B can be K1,3-covered? and we prove the following results: (1) If r = 3g + h and b = 3h + g, for some non-negative integers g and h, then there are point sets R ¿ B, like {1, 3}-equitable sets (i.e., r = 3b or b = 3r) and linearly separable sets, that can be K1,3-covered. (2) If r = 3g + h, b = 3h + g and the points in R ¿ B are in convex position, then at least r + b - 4 points can be K1,3-covered, and this bound is tight. (3) There are arbitrarily large point sets R ¿ B in general position, with r = b + 1, such that at most r + b - 5 points can be K1,3-covered. (4) If b = r = 3b, then at least 8 9 (r + b - 8) points of R ¿ B can be K1,3-covered. For r > 3b, there are too many red points and at least r - 3b of them will remain uncovered in any K1,3-covering., 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)

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)

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 Artículo científico (JournalArticle)

Coloring decompositions of complete geometric graphs

  • Huemer, Clemens|||0000-0001-7557-0823
  • Lara, Dolores
  • Rubio-Montiel, Christian
This is a post-peer-review, pre-copyedit version of an article published in Acta Mathematica Hungarica. The final authenticated version is available online at: https://doi.org/10.1007/s10474-019-00963-0, A decomposition of a non-empty simple graph G is a pair [G,P] such that P is a set of non-empty induced subgraphs of G, and every edge of G belongs to exactly one subgraph in P. The chromatic index ¿'([G,P]) of a decomposition [G,P] is the smallest number k for which there exists a k-coloring of the elements of P in such a way that for every element of P all of its edges have the same color, and if two members of P share at least one vertex, then they have different colors. A long standing conjecture of Erdos–Faber–Lovász states that every decomposition [Kn,P] of the complete graph Kn satisfies ¿'([Kn,P])=n. In this paper we work with geometric graphs, and inspired by this formulation of the conjecture, we introduce the concept of chromatic index of a decomposition of the complete geometric graph. We present bounds for the chromatic index of several types of decompositions when the vertices of the graph are in general position. We also consider the particular case when the vertices are in convex position and present bounds for the chromatic index of a few types of decompositions.
UPCommons. Portal del coneixement obert de la UPC
Publication Capítulo o parte de un libro (BookPart)

On the number of crossings in a random labeled tree

  • Arizmendi, Octavio
  • Cano, Pilar
  • Huemer, Clemens|||0000-0001-7557-0823
Octavio Arizmendi was supported by CONACYT Grant CB-2017-2018-A1-S-9764. Pilar Cano was supported by CONACYT and by projects MINECO MTM2015-63791-R and Gen. Cat. DGR 2017SGR1640. Clemens Huemer was supported by projects MINECO MTM2015-63791-R, Gen. Cat. DGR 2017SGR1336 and PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. This project has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 734922.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Antimagic labelings of caterpillars

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
A k-antimagic labeling of a graph G is an injection from E(G) to {1,2, ..., |E(G)|+k} such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to edges incident to u. We call a graph k-antimagic when it has a k-antimagic labeling, and antimagic when it is 0-antimagic. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic, but the conjecture is still open even for trees. Here we study k-antimagic labelings of caterpillars. We use algorithmic and constructive techniques, instead of the standard Combinatorial NullStellenSatz method, to prove our results: (i) any caterpillar of order n is (⌊(n−1)/2⌋−2)-antimagic; (ii) any caterpillar with a spine of order s with either at least ⌊(3s+1)/2⌋ leaves or ⌊(s−1)/2⌋ consecutive vertices of degree at most 2 at one end of a longest path, is antimagic; and (iii) if p is a prime number, any caterpillar with a spine of order p, p−1 or p−2 is 1-antimagic., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

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 a shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Problems of this type have received considerable attention recently, mostly for discrete variants of the problem. We consider a fully continuous setting, where 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. We present the first results on the computation of optimal shortcuts for general networks in this model: a polynomial time algorithm and a discretization of the problem that leads to an approximation algorithm. We also improve the general method for networks that are paths, restricted to two types of shortcuts: those with a fixed orientation and simple shortcuts., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Uniform clutters and dominating sets of graphs

  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Ruiz Muñoz, José Luis|||0000-0002-2245-7752
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, A (simple) clutter is a family of pairwise incomparable subsets of a finite set . We say that a clutter is a domination clutter if there is at least a graph such that the collection of the inclusion-minimal dominating sets of vertices of is equal to . Given a clutter , we are interested in determining if it is a domination clutter and, if this is not the case, we want to find domination clutters in some sense close to it: the domination completions of . Here we will focus on the family of clutters containing all the subsets with the same cardinality; the uniform clutters of maximum size. Specifically, we characterize those clutters in this family that are domination clutters and, in any other case, we prove that the domination completions exist. Moreover, we then demonstrate that the clutter is uniquely determined by some of its domination completions, in the sense that can be recovered from some of these domination completions by using a suitable operation between clutters., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

New production matrices for geometric graphs

  • Esteban Pascual, Guillermo
  • Huemer, Clemens|||0000-0001-7557-0823
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices., 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. This research is also supported by PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033. C. H. and R. I. S. were supported by MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1336 and 2017SGR1640. G. E. is also funded by an FPU of the Universidad de Alcalá.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Caterpillars are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a graph G is a bijection from the set of edges E(G) to {1,2,…,|E(G)|}, such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to the edges incident to u. A graph is called antimagic when it has an antimagic labeling. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic and the conjecture remains open even for trees. Here, we prove that caterpillars are antimagic by means of an O(nlogn) algorithm., Antoni Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR). Mercè Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Carlos Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Joaquin Tey is supported by project PRODEP-12612731., 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
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

  • Buchin, Kevin
  • Kostitsyna, Irina
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
Let p and q be two imprecise points, given as probability density functions on R2 , and let O be a set of disjoint polygonal obstacles in R2 . We study the problem of approximating the probability that p and q can see each other; i.e., that the segment connecting p and q does not cross any obstacle in O . To solve this problem, we first approximate each density function by a weighted set of polygons. Then we focus on computing the visibility between two points inside two of such polygons, where we can assume that the points are drawn uniformly at random. We show how this problem can be solved exactly in O((n+m)2) time, where n and m are the total complexities of the two polygons and the set of obstacles, respectively. Using this as a subroutine, we show that the probability that p and q can see each other amidst a set of obstacles of total complexity m can be approximated within error e in O(1/e3+m2/e2) time., Peer Reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Polynomially solvable cases of the bipartite traveling salesman problem

  • García, A.
  • Tejel, J.
Given two sets, R and B, consisting of n cities each, in the bipartite traveling salesman problem one looks for the shortest way of visiting alternately the cities of R and B, returning to the city of origin. This problem is known to be NP-hard for arbitrary sets R and B. In this paper we provide an O(n6) algorithm to solve the bipartite traveling salesman problem if the quadrangle property holds. In particular, this algorithm can be applied to solve in O(n6) time the bipartite traveling salesman problem in the following cases: S=R¿B is a convex point set in the plane, S=R¿B is the set of vertices of a simple polygon and V=R¿B is the set of vertices of a circular graph. For this last case, we also describe another algorithm which runs in O(n2) time.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Colored ray configurations

  • Fabila-Monroy, R.
  • García, A.
  • Hurtado, F.
  • Jaume, R.
  • Pérez-Lantero, P.
  • Saumell, M.
  • Silveira, R.I.
  • Tejel, J.
  • Urrutia, J.
We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be T(n2) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On Hamiltonian alternating cycles and paths

  • Claverol, Mercè
  • García, Alfredo
  • Garijo, Delia
  • Seara, Carlos
  • Tejel, Javier
We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O(n) and O(n2) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

  • González-Aguilar, H.
  • Orden, D.
  • Pérez-Lantero, P.
  • Rappaport, D.
  • Seara, C.
  • Tejel, J.
  • Urrutia, J.
Let P be a set of n points in the plane. We consider a variation of the classical Erdos-Szekeres problem, presenting efficient algorithms with (formula presented) running time and (formula presented) space complexity that compute: (1) A subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Packing plane spanning trees into a point set

  • Biniaz, Ahmad
  • García, Alfredo
Let P be a set of n points in the plane in general position. We show that at least ¿n/3¿ plane spanning trees can be packed into the complete geometric graph on P. This improves the previous best known lower bound O(n). Towards our proof of this lower bound we show that the center of a set of points, in the d-dimensional space in general position, is of dimension either 0 or d.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

  • Gonzalez-Aguilar, H.
  • Orden, D.
  • Perez-Lantero, P.
  • Rappaport, D.
  • Seara, C.
  • Tejel, J.
  • Urrutia, J.
Let P be a set of n points in the plane. We consider a variation of the classical Erd\H os-Szekeres problem, presenting efficient algorithms with O(n3) running time and O(n2) space complexity that compute (1) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S. We also revisit the problems of computing a maximum area orthoconvex polygon and computing a maximum area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Plane augmentation of plane graphs to meet parity constraints

  • Catana, J.C.
  • García, A.
  • Tejel, J.
  • Urrutia, J.
A plane topological graph G=(V, E) is a graph drawn in the plane whose vertices are points in the plane and whose edges are simple curves that do not intersect, except at their endpoints. Given a plane topological graph G=(V, E) and a set CG of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we say that G is topologically augmentable to meet CG if there exists a set E' of new edges, disjoint with E, such that G'=(V, E¿E') is noncrossing and meets all parity constraints. In this paper, we prove that the problem of deciding if a plane topological graph is topologically augmentable to meet parity constraints is NP-complete, even if the set of vertices that must change their parities is V or the set of vertices with odd degree. In particular, deciding if a plane topological graph can be augmented to a Eulerian plane topological graph is NP-complete. Analogous complexity results are obtained, when the augmentation must be done by a plane topological perfect matching between the vertices not meeting their parities. We extend these hardness results to planar graphs, when the augmented graph must be planar, and to plane geometric graphs (plane topological graphs whose edges are straight-line segments). In addition, when it is required that the augmentation is made by a plane geometric perfect matching between the vertices not meeting their parities, we also prove that this augmentation problem is NP-complete for plane geometric paths. For the particular family of maximal outerplane graphs, we characterize maximal outerplane graphs that are topological augmentable to satisfy a set of parity constraints. We also provide a polynomial time algorithm that decides if a maximal outerplane graph is topologically augmentable to meet parity constraints, and if so, produces a set of edges with minimum cardinality.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On plane subgraphs of complete topological drawings

  • García Olaverri A.
  • Tejel Altarriba J.
  • Pilz A.
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dnof the complete graph Knon n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least [3n/2] edges. We also address the problem of obtaining a plane subgraph of Dnwith the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete. © 2021 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Rainbow polygons for colored point sets in the plane

  • Flores-Peñaloza D.
  • Kano M.
  • Martínez-Sandoval L.
  • Orden D.
  • Tejel J.
  • Tóth C.D.
  • Urrutia J.
  • Vogtenhuber B.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let rb-index(S) denote the smallest size of a perfect rainbow polygon for a colored point set S, and let rb-index(k) be the maximum of rb-index(S) over all k-colored point sets in general position; that is, every k-colored point set S has a perfect rainbow polygon with at most rb-index(k) vertices. In this paper, we determine the values of rb-index(k) up to k=7, which is the first case where rb-index(k)¿k, and we prove that for k=5, [Formula presented] Furthermore, for a k-colored set of n points in the plane in general position, a perfect rainbow polygon with at most [Formula presented] vertices can be computed in O(nlogn) time. © 2021 Elsevier B.V.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

New production matrices for geometric graphs

  • Esteban Pascual, Guillermo
  • Huemer, Clemens
  • Silveira, Rodrigo Ignacio
We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices., 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. This research is also supported by PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033. C. H. and R. I. S. were supported by MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1336 and 2017SGR1640. G. E. is also funded by an FPU of the Universidad de Alcalá., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Map construction algorithms: a local evaluation through hiking data

  • Duran, David
  • Sacristán Adinolfi, Vera
  • Silveira, Rodrigo Ignacio
The final publication is available at Springer via http://dx.doi.org/10.1007/s10707-019-00386-7, We study five existing map construction algorithms, designed and tested with urban vehicle data in mind, and apply them to hiking trajectories with different terrain characteristics. Our main goal is to better understand the existing strategies and their limitations, in order to shed new light into the current challenges for map construction algorithms. We carefully analyze the results obtained by each algorithm focusing on the local details of the generated maps. Our analysis includes the characterization of 10 types of common artifacts, which occur in the results of more than one algorithm, and 7 algorithmic-specific artifacts, which are consequences of different algorithmic strategies. This allows us to extract systematic conclusions about the main challenges to fully automatize the construction of maps from trajectory data, to detect the strengths and weaknesses of the potential different strategies, and to suggest possible ways to design higher-quality map construction methods. We consider that this analysis will be of help for designing new and better methods that perform well in wider and more realistic contexts, not only for road map or hiking reconstruction, but also for other types of trajectory data., Departament de Matem`atiques, Universitat Polit`ecnica de Catalunya, and BGSMath, Spain. {vera.sacristan,rodrigo.silveira}@upc.edu. Partially supported by projects MTM2015-63791-R (MINECO/FEDER), Gen. Cat. 2017SGR1640. R.I. S. was also supported by MINECO through the Ram´on y Cajal program., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

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 a shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Problems of this type have received considerable attention recently, mostly for discrete variants of the problem. We consider a fully continuous setting, where 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. We present the first results on the computation of optimal shortcuts for general networks in this model: a polynomial time algorithm and a discretization of the problem that leads to an approximation algorithm. We also improve the general method for networks that are paths, restricted to two types of shortcuts: those with a fixed orientation and simple shortcuts., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Caterpillars are antimagic

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
  • Tey Carrera, Joaquín
An antimagic labeling of a graph G is a bijection from the set of edges E(G) to {1,2,…,|E(G)|}, such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to the edges incident to u. A graph is called antimagic when it has an antimagic labeling. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic and the conjecture remains open even for trees. Here, we prove that caterpillars are antimagic by means of an O(nlogn) algorithm., Antoni Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR). Mercè Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Carlos Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Joaquin Tey is supported by project PRODEP-12612731., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Uniform clutters and dominating sets of graphs

  • Martí Farré, Jaume
  • Mora Giné, Mercè
  • Ruiz Muñoz, José Luis
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, A (simple) clutter is a family of pairwise incomparable subsets of a finite set . We say that a clutter is a domination clutter if there is at least a graph such that the collection of the inclusion-minimal dominating sets of vertices of is equal to . Given a clutter , we are interested in determining if it is a domination clutter and, if this is not the case, we want to find domination clutters in some sense close to it: the domination completions of . Here we will focus on the family of clutters containing all the subsets with the same cardinality; the uniform clutters of maximum size. Specifically, we characterize those clutters in this family that are domination clutters and, in any other case, we prove that the domination completions exist. Moreover, we then demonstrate that the clutter is uniquely determined by some of its domination completions, in the sense that can be recovered from some of these domination completions by using a suitable operation between clutters., 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 Artículo científico (JournalArticle)

Capturing points with a rotating polygon (and a 3D extension)

  • Alegría Galicia, Carlos
  • Orden, David
  • Palios, Leonidas
  • Seara Ojea, Carlos
  • Urrutia Galicia, Jorge
This is a post-peer-review, pre-copyedit version of an article published in Theory of computing systems: an international journal. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00224-018-9885-y, We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a segment or a line. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space., Peer Reviewed, Postprint (author's final draft)
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 Artículo científico (JournalArticle)

Antimagic labelings of caterpillars

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
A k-antimagic labeling of a graph G is an injection from E(G) to {1,2, ..., |E(G)|+k} such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to edges incident to u. We call a graph k-antimagic when it has a k-antimagic labeling, and antimagic when it is 0-antimagic. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic, but the conjecture is still open even for trees. Here we study k-antimagic labelings of caterpillars. We use algorithmic and constructive techniques, instead of the standard Combinatorial NullStellenSatz method, to prove our results: (i) any caterpillar of order n is (⌊(n−1)/2⌋−2)-antimagic; (ii) any caterpillar with a spine of order s with either at least ⌊(3s+1)/2⌋ leaves or ⌊(s−1)/2⌋ consecutive vertices of degree at most 2 at one end of a longest path, is antimagic; and (iii) if p is a prime number, any caterpillar with a spine of order p, p−1 or p−2 is 1-antimagic., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A new lower bound on the maximum number of plane graphs using production matrices

  • Huemer, Clemens
  • Pilz, Alexander
  • Silveira, Rodrigo Ignacio
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We use the concept of production matrices to show that there exist sets of n points in the plane that admit ¿(42.11n ) crossing-free geometric graphs. This improves the previously best known bound of ¿(41.18n ) by Aichholzer et al. (2007)., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

K-1,K-3-covering red and blue points in the plane

  • Ábrego, Bernardo M.
  • Fernández Merchant, Silvia
  • Kano, Mikio
  • Orden, David
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
  • Tejel Altarriba, Francisco Javier
We say that a finite set of red and blue points in the plane in general position can be K1,3-covered if the set can be partitioned into subsets of size 4, with 3 points of one color and 1 point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set R of r red points and a set B of b blue points in the plane in general position, how many points of R ¿ B can be K1,3-covered? and we prove the following results: (1) If r = 3g + h and b = 3h + g, for some non-negative integers g and h, then there are point sets R ¿ B, like {1, 3}-equitable sets (i.e., r = 3b or b = 3r) and linearly separable sets, that can be K1,3-covered. (2) If r = 3g + h, b = 3h + g and the points in R ¿ B are in convex position, then at least r + b - 4 points can be K1,3-covered, and this bound is tight. (3) There are arbitrarily large point sets R ¿ B in general position, with r = b + 1, such that at most r + b - 5 points can be K1,3-covered. (4) If b = r = 3b, then at least 8 9 (r + b - 8) points of R ¿ B can be K1,3-covered. For r > 3b, there are too many red points and at least r - 3b of them will remain uncovered in any K1,3-covering., Peer Reviewed, Postprint (published version)
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 Artículo científico (JournalArticle)

Coloring decompositions of complete geometric graphs

  • Huemer, Clemens
  • Lara, Dolores
  • Rubio-Montiel, Christian
This is a post-peer-review, pre-copyedit version of an article published in Acta Mathematica Hungarica. The final authenticated version is available online at: https://doi.org/10.1007/s10474-019-00963-0, A decomposition of a non-empty simple graph G is a pair [G,P] such that P is a set of non-empty induced subgraphs of G, and every edge of G belongs to exactly one subgraph in P. The chromatic index ¿'([G,P]) of a decomposition [G,P] is the smallest number k for which there exists a k-coloring of the elements of P in such a way that for every element of P all of its edges have the same color, and if two members of P share at least one vertex, then they have different colors. A long standing conjecture of Erdos–Faber–Lovász states that every decomposition [Kn,P] of the complete graph Kn satisfies ¿'([Kn,P])=n. In this paper we work with geometric graphs, and inspired by this formulation of the conjecture, we introduce the concept of chromatic index of a decomposition of the complete geometric graph. We present bounds for the chromatic index of several types of decompositions when the vertices of the graph are in general position. We also consider the particular case when the vertices are in convex position and present bounds for the chromatic index of a few types of decompositions., 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)

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
Publication Artículo científico (JournalArticle)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14]., A. Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR); M. Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT; and C. Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9–14]., Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A note on flips in diagonal rectangulations

  • Cardinal, Jean
  • Sacristán Adinolfi, Vera
  • Silveira, Rodrigo Ignacio
Rectangulations are partitions of a square into axis-aligned rectangles. A number of results provide bijections between combinatorial equivalence classes of rectangulations and families of pattern-avoiding permutations. Other results deal with local changes involving a single edge of a rectangulation, referred to as flips, edge rotations, or edge pivoting. Such operations induce a graph on equivalence classes of rectangulations, related to so-called flip graphs on triangulations and other families of geometric partitions. In this note, we consider a family of flip operations on the equivalence classes of diagonal rectangulations, and their interpretation as transpositions in the associated Baxter permutations, avoiding the vincular patterns { 3{14}2, 2{41}3 }. This complements results from Law and Reading (JCTA, 2012) and provides a complete characterization of flip operations on diagonal rectangulations, in both geometric and combinatorial terms., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

On the number of crossings in a random labeled tree

  • Arizmendi, Octavio
  • Cano, Pilar
  • Huemer, Clemens
Octavio Arizmendi was supported by CONACYT Grant CB-2017-2018-A1-S-9764. Pilar Cano was supported by CONACYT and by projects MINECO MTM2015-63791-R and Gen. Cat. DGR 2017SGR1640. Clemens Huemer was supported by projects MINECO MTM2015-63791-R, Gen. Cat. DGR 2017SGR1336 and PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. This project has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 734922., Postprint (author's final draft)
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 Artículo científico (JournalArticle)

Convex quadrangulations of bichromatic point sets

  • Pilz, Alexander
  • Seara Ojea, Carlos
Electronic version of an article published as International journal of computational geometry and applications, 5 May 2020, vol. 29, núm. 4, p. 289-299. Article DOI 10.1142/S0218195919500109 © 2020 copyright World Scientific Publishing Company. Journal URL: https://www.worldscientific.com/doi/abs/10.1142/S0218195919500109, We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set S of points with each point either red or blue, does there exist a convex quadrangulation of S in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets., 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)

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 Artículo científico (JournalArticle)

A comparative analysis of trajectory similarity measures

  • Tao, Yaguang
  • Both, Alan
  • Silveira, Rodrigo Ignacio
  • Sijben, Stef
  • Buchin, Kevin
  • Purves, Ross S.
  • Laube, Patrick
  • Peng, Dongliang
  • Toohey, Kevin
  • Duckham, Matt
Computing trajectory similarity is a fundamental operation in movement analytics, required in search, clustering, and classification of trajectories, for example. Yet the range of different but interrelated trajectory similarity measures can be bewildering for researchers and practitioners alike. This paper describes a systematic comparison and methodical exploration of trajectory similarity measures. Specifically, this paper compares five of the most important and commonly used similarity measures: dynamic time warping (DTW), edit distance (EDR), longest common subsequence (LCSS), discrete Fréchet distance (DFD), and Fréchet distance (FD). The paper begins with a thorough conceptual and theoretical comparison. This comparison highlights the similarities and differences between measures in connection with six different characteristics, including their handling of a relative versus absolute time and space, tolerance to outliers, and computational efficiency. The paper further reports on an empirical evaluation of similarity in trajectories with contrasting properties: data about constrained bus movements in a transportation network, and the unconstrained movements of wading birds in a coastal environment. A set of four experiments: a. creates a measurement baseline by comparing similarity measures to a single trajectory subjected to various transformations; b. explores the behavior of similarity measures on network-constrained bus trajectories, grouped based on spatial and on temporal similarity; c. assesses similarity with respect to known behavioral annotations (flight and foraging of oystercatchers); and d. compares bird and bus activity to examine whether they are distinguishable based solely on their movement patterns. The results show that in all instances both the absolute value and the ordering of similarity may be sensitive to the choice of measure. In general, all measures were more able to distinguish spatial differences in trajectories than temporal differences. The paper concludes with a high-level summary of advice and recommendations for selecting and using trajectory similarity measures in practice, with conclusions spanning our three complementary perspectives: conceptual, theoretical, and empirical., This work was supported by the Ministry of Economy and Competitiveness (MINECO) [MTM2015-63791-R]; CRC for Spatial Information [Rapid Spatial Analytics]., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Hamiltonicity for convex shape Delaunay and Gabriel graphs

  • Bose, Prosenjit
  • Cano Vila, María del Pilar
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, 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 \(\mathcal {C}\) . Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- \({DG}_{\mathcal {C}}(S)\) , has vertex set S and edge pq provided that there exists some homothet of \(\mathcal {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 k- \({GG}_{\mathcal {C}}(S)\) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of \(\mathcal {C}\) with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- \({GG}_{\mathcal {C}}(S)\) is Hamiltonian. Since k- \({GG}_{\mathcal {C}}(S)\) \(\subseteq \) k- \({DG}_{\mathcal {C}}(S)\) , all results carry over to k- \({DG}_{\mathcal {C}}(S)\) . In particular, we give upper bounds of 24 for every \(\mathcal {C}\) and 15 for every point-symmetric \(\mathcal {C}\) . We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for \(t \ge 10)\) . These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs., 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)

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
Publication Artículo científico (JournalArticle)

Non-crossing paths with geographic constraints

  • Silveira, Rodrigo Ignacio
  • Speckmann, Bettina
  • Verbeek, Kevin
A geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geographic networks: can a given geographic network be drawn without crossings? We focus on the seemingly simple setting where each region is a unit length vertical segment, and one wants to connect pairs of segments with a path that lies inside the convex hull of the two segments. We prove that when paths must be drawn as straight line segments, it is NP-complete to determine if a crossing-free solution exists. In contrast, we show that when paths must be monotone curves, the question can be answered in polynomial time. In the more general case of paths that can have any shape, we show that the problem is polynomial under certain assumptions., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

  • Buchin, Kevin
  • Kostitsyna, Irina
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio
Let p and q be two imprecise points, given as probability density functions on R2 , and let O be a set of disjoint polygonal obstacles in R2 . We study the problem of approximating the probability that p and q can see each other; i.e., that the segment connecting p and q does not cross any obstacle in O . To solve this problem, we first approximate each density function by a weighted set of polygons. Then we focus on computing the visibility between two points inside two of such polygons, where we can assume that the points are drawn uniformly at random. We show how this problem can be solved exactly in O((n+m)2) time, where n and m are the total complexities of the two polygons and the set of obstacles, respectively. Using this as a subroutine, we show that the probability that p and q can see each other amidst a set of obstacles of total complexity m can be approximated within error e in O(1/e3+m2/e2) time., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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)