Pasar al contenido principal

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Channel Selection in Uncoordinated IEEE 802.11 Networks Using Graph Coloring

  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
  • Marsá-Maestre, Iván
  • de la Hoz, Enrique
  • Orden, David
  • Herranz-Oliveros, David
[EN] One of the big challenges in decentralized Wi-Fi networks is how to select channels for the different access points (APs) and their associated stations (STAs) in order to minimize interference and hence maximize throughput. Interestingly enough, de facto standards in terms of uncoordinated channel selection are quite simple, and in many cases result in fairly suboptimal channel allocations. Here, we explore how graph coloring can be used to evaluate and inform decisions on Wi-Fi channel selection in uncoordinated settings. Graph coloring, in its most basic form, is a classic mathematical problem where colors have to be assigned to nodes in a graph while avoiding assigning the same color to adjacent nodes. In this paper, we modeled Wi-Fi uncoordinated channel selection as a graph coloring problem and evaluated the performance of different uncoordinated channel selection techniques in a set of representative scenarios of residential buildings. The results confirm some of the widely accepted consensus regarding uncoordinated channel selection but also provide some new insights. For instance, in some settings, it would be better to delegate the decision on which channel to use to transmit the STAs, rather than having the AP make the decision on its own, which is the usual way., This publication is part of Project TED2021-131387B-I00 funded by MCIN/AEI/10.13039/501100011033 and by the European Union "NextGenerationEU"/PRTR and of Project PID2021-123168NB-I00 funded by MCIN/AEI/10.13039/501100011033/FEDER, UE. Ivan Marsa-Maestre and David Orden are partially funded by Project SB-PLY/19/180501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER and by Project WiDAI (CM/JIN/2021-004) of the Comunidad de Madrid and University of Alcala. Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, and David Herranz-Oliveros are also funded by Project PID2019-104855RB-I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation. David Orden is also partially supported by Project PID2019-104129GB-I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation. The APC was funded by Project TED2021-131387B-I00 funded by MCIN/AEI/10.13039/501100011033 and by the European Union "NextGenerationEU"/PRTR.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

IEEE 802.11 graph models

  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
  • Marsa-Maestre, Ivan
  • Cruz-Piris, Luis
  • Orden, David
  • Tejedor-Romero, Marino
[EN] There are several recent research lines addressing Wi-Fi network planning and optimiza-tion, both in terms of channel assignment and access point deployment. The problem with these works is that evaluation is usually performed with specific and closed models regarding signal prop-agation, throughput computation, and utility definition. Also, many of the models in the literature make assumptions about the role of wireless stations, or the co-channel interference, which-while being valid in the context of a single research work-makes very difficult to compare different approaches, to re-use concepts from previous mechanisms to create new ones, or to generalize mechanisms to other scenarios. This makes the different research lines in Wi-Fi network planning and optimization progress in an isolated manner.This paper aims to address such a recurring problem by proposing a graph-based generic model for Wi-Fi utility computation in network planning scenarios, as well as providing a collection of scenario graphs which may be used to benchmark different planning and optimization approaches. Experiments are conducted to show the validity of the model and the significance of its features, along with its extensibility to other scenarios., This work has been partially funded by Projects PID2019-10 4855RB-I00/AEI/10.13039/501100011033 and PID2019-10412 9GB-I00/AEI/10.13039/501100011033, by Project SBPLY/19/180501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER, by Projects UCeNet (CM/JIN/2019-031) and WiDAI (CM/JIN/2021-004) of the Comunidad de Madrid and University of Alcala, and by H2020-MSCA-RISE project 734922 - CONNECT. The publication is also part of project TED2021-131387B-I00 funded by MCIN/AEI/10.13039/501100011033 and by the European Union "NextGenerationEU"/PRTR and of project PID2021-123168NB-I00 funded by MCIN/AEI/10.13039/50110001103 3/FEDER, UE.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Distributed Remote E-Voting System Based on Shamir&apos, s Secret Sharing Scheme

  • Tejedor-Romero, Marino
  • Orden, David
  • Marsa-Maestre, Ivan
  • Junquera-Sanchez, Javier
  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
[EN] A number of e-voting systems have been proposed in the last decades, attracting the interest of the research community. The challenge is far from being fully addressed, especially for remote systems. In this work, we propose DiverSEC, a distributed, remote e-voting system based on Shamir secret sharing, operations in Galois field and mixnets, which enables end-to-end vote verification. Parties participate as nodes in the network, protecting their interests and ensuring process integrity due to the conflicting interests. The threat model is very conservative, not letting even the most privileged actors to compromise votes privacy or integrity. Security in depth is implemented, overlapping different mechanisms to offer guarantees even in the most adverse operating conditions. The main contributions of the resulting system are our proposal for secret-sharing among the political parties, which guarantees that no party can compromise the integrity of the ballot without being detected and identified in real time, and the computational and architectural scalability of the proposal, which make it easy to implement., M.T.-R. is funded by a predoctoral grant from the University of Alcala. M.T.-R., I.M.-M. and J.M.G.-G. are partially funded by Project PID2019-104855RB-I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, by Project SBPLY/19/180501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER and by Project UCeNet (CM/JIN/2019-031) of the Comunidad de Madrid and University of Alcala. D.O. is partially supported by Project PID2019-104129GB-I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and by H2020-MSCA-RISE project 734922-CONNECT.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

On the Benefits of Channel Bonding in Dense, Decentralized Wi-Fi 4 Networks

  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
  • Marsa-Maestre,Ivan
  • Orden, David
  • Fernandez, Susel
  • Tejedor-Romero, Marino
[EN] Channel bonding is a technique first defined in the IEEE 802.11n standard to increase the throughput in wireless networks by means of using wider channels. In IEEE 802.11n (nowadays also known as Wi-Fi 4), it is possible to use 40 MHz channels instead of the classical 20 MHz channels. Although using channel bonding can increase the throughput, the classic 802.11 setting only allows for two orthogonal channels in the 2.4 GHz frequency band, which is not enough for proper channel assignment in dense settings. For that reason, it is commonly accepted that channel bonding is not suitable for this frequency band. However, to the best of our knowledge, there is not any accurate study that deals with this issue thoroughly. In this work, we study in depth the effect of channel bonding in Wi-Fi 4 dense, decentralized networks operating in the 2.4 GHz frequency band. We confirm the negative effect of using channel bonding in the 2.4 GHz frequency band with 11 channels which are 20 MHz wide (as in North America), but we also show that when there are 13 or more channels at hand (as in many other parts of the world, including Europe and Japan), the use of channel bonding yields consistent throughput improvements. For that reason, we claim that the common assumption of not considering channel bonding in the 2.4 GHz band should be revised., Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, David Orden, and Susel Fernandez were partially funded by Project SBPLY/19/180 501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER and by Project UCeNet (CM/JIN/2019-031) of the Comunidad de Madrid and University of Alcala. Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, and Susel Fernandez were also funded by Project PID2019-104855RB-I00/AEI/10.130 39/501 100 011 033 of the Spanish Ministry of Science and Innovation. David Orden was also partially supported by Project PID2019-104129GB-I00/AEI/10.130 39/501 100 011 033 of the Spanish Ministry of Science and Innovation and by H2020-MSCA-RISE Project 734922 - CONNECT. Marino Tejedor-Romero was funded by a predoctoral contract from University of Alcala.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Graphs with isolation number equal to one third of the order

  • Lemańska, Magdalena
  • Mora, Mercè
  • Souto Salorio, María José
© 2024. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/. This version of the article has been accepted for publication in Discrete Mathematics (ISSN 2578-9252). The Version of Record is available online at 10.1016/j.disc.2024.113903., [Absctract]: A set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by ι(G), is the minimum cardinality of an isolating set of G. It`s known that ι(G) ≤ n/3, if G is a connected graph of order n, n ≥ 3, distinct from C5. The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number equal to n/3. Moreover, we provide a family of general graphs attaining this upper bound on the isolation number., Partially supported by projects PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation and Gen.Cat. DGR2021SGR00266. Partially supported by project PID2020-113230RB-C21 of the Spanish Ministry of Science and Innovation.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Resolving Sets Tolerant to Failures in Three-Dimensional Grids

  • Mora, Mercè
  • Souto Salorio, María José
  • Tarrío-Tobar, Ana D.
[Abstract] An ordered set S of vertices of a graph G is a resolving set for G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set. In this paper we study resolving sets tolerant to several failures in three-dimensional grids. Concretely, we seek for minimum cardinality sets that are resolving after removing any k vertices from the set. This is equivalent to finding (k+1)-resolving sets, a generalization of resolving sets, where, for every pair of vertices, the vector of distances to the vertices of the set differs in at least k+1 coordinates. This problem is also related with the study of the (k+1)-metric dimension of a graph, defined as the minimum cardinality of a (k+1)-resolving set. In this work, we first prove that the metric dimension of a three-dimensional grid is 3 and establish some properties involving resolving sets in these graphs. Secondly, we determine the values of k≥1 for which there exists a (k+1)-resolving set and construct such a resolving set of minimum cardinality in almost all cases., 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. M. Mora is supported by projects H2020-MSCA-RISE-2016-734922 CONNECT, PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation and Gen.Cat. DGR2017SGR1336; M. J. Souto-Salorio is supported by project PID2020-113230RB-C21 of the Spanish Ministry of Science and Innovation. Open Access funding provided thanks to the CRUECSIC agreement with Springer Nature, Generalitat de Catalunya; DGR2017SGR1336
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
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 paper, 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 ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. 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 to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. 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 research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Computing largest minimum color-spanning intervals of imprecise points

  • Acharyya, Ankush
  • Keikha, Vahideh
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in time when , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard., A. Acharyya was supported by the DST-SERB grant number SRG/2022/002277. V. Keikha was supported by the CAS PPPLZ grant L100302301, and the institutional support RVO: 67985807. M. Saumell was supported by the Czech Science Foundation, grant number 23-04949X. R. Silveira was partially supported by grant PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

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 Mathematics, 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. Each pair of matched points p¿R and q¿B induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point., We thank the GeoGebra open source software and its developers [17]. S. B. was supported in part by NSF award CCF-1718994. D. F-P. was partially supported by PAPIIT IN120520 (UNAM, Mexico). C. H. and C. S. were partially supported by project MICINN 2020-2024 PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. P. P-L. was partially supported by projects DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

  • Alegría Galicia, Carlos
  • Orden Martin, David
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
This is a post-peer-review, pre-copyedit version of an article published in Journal of Global Optimization. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10898-020-00953-5, Let P be a set of n points in the plane. We compute the value of ¿¿[0,2p) for which the rectilinear convex hull of P, denoted by RHP(¿), has minimum (or maximum) area in optimal O(nlogn) time and O(n) space, improving the previous O(n2) bound. Let O be a set of k lines through the origin sorted by slope and let ai be the sizes of the 2k angles defined by pairs of two consecutive lines, i=1,…,2k. Let Ti=p-ai and T=min{Ti:i=1,…,2k}. We obtain: (1) Given a set O such that T=p2, we provide an algorithm to compute the O-convex hull of P in optimal O(nlogn) time and O(n) space; If T<p2, the time and space complexities are O(nTlogn) and O(nT) respectively. (2) Given a set O such that T=p2, we compute and maintain the boundary of the O¿-convex hull of P for ¿¿[0,2p) in O(knlogn) time and O(kn) space, or if T<p2, in O(knTlogn) time and O(knT) space. (3) Finally, given a set O such that T=p2, we compute, in O(knlogn) time and O(kn) space, the angle ¿¿[0,2p) such that the O¿-convex hull of P has minimum (or maximum) area over all ¿¿[0,2p)., Carlos Alegría: Research supported in part by UNAM Project PAEP, and by MIUR Proj. “AHeAD” No. 20174LF3T8. David Orden: Research supported by Projects MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE), and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACYT 80268, PAPPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica UNAM. 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
Publicación Artículo científico (JournalArticle)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
The version of record of this article, first published in Journal of Combinatorial Optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10878-023-01010-z, Given n > 0, let S ¿ [0,1]2 be a set of n points, chosen uniformly at random. 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 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 axis-aligned rectangles that cover exactly two points of S of the same color, and is strong in the sense that all of 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., Author Corujo was supported by grants from the Université Paris-Dauphine (France) and the ITI IRMIA++. Author Flores-Peñaloza was supported by project PAPIIT IN120520 (UNAM, Mexico). Author Huemer was supported by projects PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2021-SGR-00266. Author Pérez-Lantero was supported by projects CONICYT FONDECYT/Regular 1160543 (Chile), DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Author Seara was supported by project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/ 501100011033 and Gen. Cat. DGR 2021-SGR-00266.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Geometric thickness of multigraphs is ¿R-Complete

  • Förster, Henry
  • Kindermann, Philipp
  • Miltzow, Tillmann
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Terziadis, Soeren
  • Vogtenhuber, Birgit
We say that a (multi)graph has geometric thickness t if there exists a straight-line drawing and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t. This problem was shown to be NP-hard for (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is -complete already for thickness 30. Moreover, our reduction shows that the problem is -complete for 4392-planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are -complete., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The complexity of geodesic spanners using Steiner points

  • de Berg, Sarita
  • Ophelders, Tim
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Staals, Frank
  • Wulms, Jules
A geometric t-spanner G on a set S of n point sites in a metric space P is a subgraph of the complete graph on S such that for every pair of sites p,q the distance in G is a most t times the distance d(p,q) in P. We call a connection between two sites a link. In some settings, such as when P is a simple polygon with m vertices and a link is a shortest path in P, links can consist of T(m) segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce k Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. Surprisingly, we show that Steiner points have only limited utility. For a spanner that uses k Steiner points, we provide an ¿(nm/k) lower bound on the worst-case complexity of any (3 - e)spanner, and an ¿(mn1/(t+1)/k1/(t+1)) lower bound on the worst-case complexity of any (t - e)spanner, for any constant e ¿ (0,1) and integer constant t = 2. These lower bounds hold in all settings. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a 3-spanner with a given maximum complexity using k Steiner points. On the positive side, for trees we show how to build a 2t-spanner that uses k Steiner points of complexity O(mn1/t/k1/t + nlog(n/k)), for any integer t = 1. We generalize this result to forests, and apply it to obtain a 2v2t-spanner in a simple polygon with total complexity O(mn1/t(logk)1+1/t/k1/t + nlog2 n). When a link in the spanner can be any path between two sites, we show how to improve the spanning ratio in a simple polygon to (2k + e), for any constant e ¿(0,2k), and how to build a 6t-spanner in a polygonal domain with the same complexity., Tim Ophelders: partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

New cyclic Kautz digraphs with optimal diameter

  • Böhmová, Katerina
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Huemer, Clemens|||0000-0001-7557-0823
We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' M C K ( d , l ) , and it is derived from the Kautz digraphs K ( d , l ) and from the so-called cyclic Kautz digraphs C K ( d , l ) . The cyclic Kautz digraphs C K ( d , l ) were defined as the digraphs whose vertices are labeled by all possible sequences a 1 … a l of length l , such that each character a i is chosen from an alphabet of d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a 1 ¿ a l . Their arcs are between vertices a 1 a 2 … a l and a 2 … a l a l + 1 , with a 1 ¿ a l and a 2 ¿ a l + 1 . Since C K ( d , l ) do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that M C K ( d , l ) are d -out-regular. Moreover, for t = 1 , we compute the number of vertices of the iterated line digraphs L t ( C K ( d , l ) ) ., The research of C. Dalfó has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under projects MTM2017-83271-R and PGC2018-095471-B-I00. The research of C. Huemer was supported by PID2019-104129GB-I00/AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922 .
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On weighted sums of numbers of convex polygons in point sets

  • Huemer, Clemens|||0000-0001-7557-0823
  • Oliveros, Deborah
  • Pérez Lantero, Pablo
  • Torra Clotet, Ferran
  • Vogtenhuber, Birgit
The version of record of this article, first published in Discrete & Computational Geometry, is available online at Publisher’s website: https://doi.org/10.1007/s00454-022-00395-8, Let S be a set of n points in general position in the plane, and let Xk,(S) be the number of convex k-gons with vertices in S that have exactly points of S in their interior. We prove several equalities for the numbers Xk,(S). This problem is related to the Erd¿os–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well., Research of C.H. was partially supported by project MTM2015-63791-R (MINECO/ FEDER), PID-2019-104129GB-I00/MCIN/AEI/10.13039/501100011033, and by project Gen. Cat. DGR 2017SGR1336. D.O. was partially supported by project PAPIIT IG100721 and CONACyT 282280. P. P-L. was partially supported by project DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Research of B.V. was partially supported by the Austrian Science Fund (FWF) within the collaborative DACH project Arrangements and Drawings as FWF Project I 3340-N35. We thank an anonymous referee for helpful comments. This project has been supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación Contribución de congreso (ConferenceOutput)

Dynamic embeddings of dynamic single-source upward planar graphs

  • van der Hoog, Ivor
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Rotenberg, Eva
A directed graph G is upward planar if it admits a planar embedding where each edge is y-monotone. Unlike planarity testing, upward planarity testing is NP-hard except in restricted cases, such as when the graph has the single-source property (i.e., each connected component has one source). In this paper, we present a dynamic data structure for maintaining an upward combinatorial embedding -¿E (G) of a single-source upward planar graph subject to edge deletions, edge contractions, directed edge insertions across a face, and single-source-preserving vertex splits through specified corners (i.e., the gaps between pairs of consecutive edges that share a vertex and a face). We furthermore support changes to the embedding -¿E (G) in the form of subgraph flips that mirror or slide the placement of a subgraph that is connected to the rest of the graph via at most two vertices. Updates that are incompatible with the current upward planar embedding are identified and rejected. All update operations are supported as long as the graph remains upward planar. In addition, we support queries that can tell whether two vertices can be connected with a directed edge while the graph remains single-source (we call these uplinkability queries). If a pair of vertices are not uplinkable, we facilitate one-flip-linkable queries: These point to a flip that makes them uplinkable, if any such flip exists. We dynamically maintain a linear-size data structure on G which supports incidence queries between a vertex and a face, and uplinkability queries for vertex pairs. We support all updates and queries in O(log2 n) worst-case time., This research was supported by Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic Network Analysis”. Ivor van der Hoog: This project has additionally received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Eva Rotenberg: This research was additionally supported by Carlsberg Foundation Young Researcher Fellowship CF21-0302 “Graph Algorithms with Geometric Applications”., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Continuous mean distance of a weighted graph

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances between all pairs of vertices. This parameter provides a natural measure of the compactness of the graph, and has been intensively studied, together with several variants, including its version for weighted graphs. The continuous analog of the (discrete) mean distance is the mean of the distances between all pairs of points on the edges of the graph. Despite being a very natural generalization, to the best of our knowledge this concept has been barely studied, since the jump from discrete to continuous implies having to deal with an infinite number of distances, something that increases the difficulty of the parameter. In this paper, we show that the continuous mean distance of a weighted graph can be computed in time roughly quadratic in the number of edges, by two different methods that apply fundamental concepts in discrete algorithms and computational geometry. We also present structural results that allow for a faster computation of this continuous parameter for several classes of weighted graphs. Finally, we study the relation between the (discrete) mean distance and its continuous counterpart, mainly focusing on the relevant question of convergence when iteratively subdividing the edges of the weighted graph., This work was supported by grants PID2019-104129GB-I00/ AEI/ 10.13039/501100011033, Gen. Cat. 2017SGR1640, and PID2019-103900GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the metric representation of the vertices of a graph

  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Puertas González, María Luz
The version of record is available online at: http://dx.doi.org/10.1007/s40840-023-01582-3, The metric representation of a vertex u in a connected graph G respect to an ordered vertex subset is the vector of distances . A vertex subset W is a resolving set of G if , for every with . Thus, a resolving set with n elements provides a set of metric representation vectors with cardinal equal to the order of the graph. In this paper, we address the reverse point of view; that is, we characterize the finite subsets that are realizable as the set of metric representation vectors of a graph G with respect to some resolving set W. We also explore the role that the strong product of paths plays in this context. Moreover, in the case , we characterize the sets that are uniquely realizable as the set of metric representation vectors of a graph G with respect to a resolving set W., This work was partially supported by the grants of the Spanish Ministry of Science and Innovation PID2021-123278OB-I00 and PID2019-104129GB-I00, both funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, and Gen. Cat. DGR 2021-SGR-00266., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2023 Elsevier. 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 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 , which is a shortest path from s to t in the space; a weighted shortest vertex path , which is an any-angle shortest path; and a weighted shortest grid path , which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios , , , which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that in the worst case, and this is tight. As a corollary, for the weighted any-angle path we obtain the approximation result ., 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 also funded by an FPU of the Universidad de Alcalá., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Shortest coordinated motion for square robots

  • Esteban Pascual, Guillermo
  • Halperin, Dan
  • Ruíz, Víctor
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations, find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. We present an adaptation of the tools developed for the case of discs by Kirkpatrick and Liu [Characterizing minimum-length coordinated motions for two discs. Proceedings 28th CCCG, 252-259, 2016; CoRR abs/1607.04005, 2016.] to the case of squares. Certain aspects of the case of squares are more complicated, requiring additional and more involved arguments over the case of discs. Our contribution can serve as a basic component in optimizing the coordinated motion of two squares among obstacles, as well as for local planning in sampling-based algorithms, which are often used in practice, in the same setting., Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Rectilinear convex hull of points in 3D and applications

  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
The version of record of this article, first published in Journal of global optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10898-024-01402-3, Let P be a set of n points in R3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal O(n log n) time and O(n) space algorithm to compute RCH(P). We also obtain an efficient O(n log2 n) time and O(n log n) space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate R3 around the Z-axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in R3. Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in R3., Pablo Pérez-Lantero: Partially supported by project DICYT 042332PL Vicerrectoría de Investigación Desarrollo e Innovación USACH (Chile). Carlos Seara: Partially supported by project PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Jorge Urrutia: Supported in part by SEP-CONACYT of México, Proyecto 80268, and by PAPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica, UNAM., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The oriented chromatic number of the hexagonal grid is 6

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χo(F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H2, Bielak (2006) proved that 5 ≤χo(H2) ≤ 6. Here we close the gap by showing that χo(H2) ≥ 6., This research was supported by project PID2019-104129GB-I00, funded by MICIU/AEI/10.13039/501100011033, and by Universitat Politècnica de Catalunya under grant AGRUPS-2023., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Coloraciones por entornos en jaulas de Moore

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Araujo Pardo, Gabriela
A k-coloring of a graph G is a k-partition = S1 Sk of V(G) into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices uv belonging to the same color Si, the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number, denoted by NL(G), is the minimum cardinality of a neighbor-locating coloring of G. In this paper we study the neighbor-locating coloring of graphs that are Moore cages.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Graph sampling for map comparison

  • Aguilar Larruy, Jordi
  • Buchin, Kevin
  • Buchin, Maike
  • Hosseini Sereshgi, Erfan
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Wenk, Carola
Comparing two road maps is a basic operation that arises in a variety of situations. A map comparison method that is commonly used, mainly in the context of comparing reconstructed maps to ground-truth maps, is based on graph sampling. The essential idea is to first compute a set of point samples on each map and then to match pairs of samples—one from each map—in a one-to-one fashion. For deciding whether two samples can be matched, different criteria, e.g., based on distance or orientation, can be used. The total number of matched pairs gives a measure of how similar the maps are. Since the work of Biagioni and Eriksson [11, 12], graph sampling methods have become widely used. However, there are different ways to implement each of the steps, which can lead to significant differences in the results. This means that conclusions drawn from different studies that seemingly use the same comparison method cannot necessarily be compared. In this work we present a unified approach to graph sampling for map comparison. We present the method in full generality, discussing the main decisions involved in its implementation. In particular, we point out the importance of the sampling method (GEO vs. TOPO) and that of the matching definition, discussing the main options used, and proposing alternatives for both key steps. We experimentally evaluate the different sampling and matching options considered on map datasets and reconstructed maps. Furthermore, we provide a code base and an interactive visualization tool to set a standard for future evaluations in the field of map construction and map comparison., E.H.S. and C.W. were partially supported by National Science Foundation grant CCF 1637576. R.I.S. was partially supported by project PID2019-104129GB-I00/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Graphs attaining the upper bound on the isolation number

  • Lemanska, Magdalena
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Souto Salorio, María josé
A set D of vertices of a graph is isolating if the set of vertices not belonging to D or not having a neighbour in D is independent. The isolation number of a graph G, denoted by ¿(G), is the minimum cardinality of an isolating set. It is known that ¿(G) = n/3 if G is a connected graph of order n, n = 3, different from a cycle of order 5. Moreover, trees attaining this upper bound have been characterized. In this work we characterize all unicyclic and block graphs of order n such that ¿(G) = n/3., Partially supported by projects PID2020-113230RB-C21 and PID2019-104129GBI00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and Gen.Cat. DGR2021-SGR-00266., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Tuttle, Tyler
Let ¿(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x,y ¿ S, where every geodesic disk containing x and y contains ¿(n) points of S. We establish upper and lower bounds for ¿(n), and show that n 5 +1 = ¿(n) = n 4 +1. We also show that there always exist two points x,y ¿ S such that every geodesic disk with x and y on its boundary contains at least 16 665 (n - 2) ˜ n-2 41.6 points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of n 3 +1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of n-2 two-colored version of the problem., G. E., D. O. and R. S. are partially supported by grants PID2019-104129GB-I00 and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. P. B. and T. T. are supported in part by NSERC., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

ROADSTER: improved algorithms for subtrajectory clustering and map construction

  • Buchin, Kevin
  • Buchin, Maike
  • Gudmundsson, Joachim
  • Hendriks, Jorren
  • Hosseini Sereshgi, Erfan
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Sleijster, Jorrick
  • Staals, Frank
  • Wenk, Carola
The challenge of map construction involves creating a representation of a travel network using data from the paths traveled by entities within the network. Although numerous algorithms for constructing maps can effectively piece together the overall layout of a network, accurately capturing smaller details like the positions of intersections and turns tends to be more difficult. This difficulty is especially pronounced when the data is noisy or collected at irregular intervals. In this paper we present Roadster, a map construction system that combines efficient cluster computation and a sophisticated method to construct a map from a set of such clusters. First, edges are extracted by producing a number of subtrajectory clusters, of varying widths, which naturally correspond to paths in the network. Second, representative paths are extracted from the candidate clusters. The geometry of each representative path is improved in a process involving several stages, that leads to map edges. The rich information obtained from the clustering process is also used to compute map vertices, and to finally connect them using map edges. An experimental evaluation of Roadster, using vehicle and hiking GPS data, shows that the system can produce maps of higher quality than previous methods., We thank Roel Jacobs for the initial implementation of the bundling and map construction algorithms, and Vera Sacristán for her participation in an earlier version of this work. We also thank Songtao He for providing us with Roadrunner’s reconstructed map on Chicago (He et al., 2018). Yes. E. Hosseini Sereshgi and C. Wenk were partially supported by National Science Foundation, United States grants CCF-1637576 and CCF-2107434. R.I. Silveira was partially supported by MICINN through grant PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Edge-minimum saturated k-planar drawings

  • Chaplick, Steven
  • Klute, Fabian Maximilian|||0000-0002-7791-3604
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Rollin, Jonathan
  • Ueckerdt, Torsten
F. Klute was supported by the Netherlands Organisation for Scientific Research (NWO) project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510. I. Parada was supported by the Margarita Salas Fellowship 2021UPC‐MS‐67392 funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). F. Klute and I. Parada were supported by grant PID2019104129GB‐I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles

  • Alegria, Carlos
  • Dallant, Justin
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull witharbitraryorientation for asetofsegmentsandcircles.Wedescribe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to 2p. We first consider a set of n segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal (n logn) time and O(na(n)) space, where a(n) is the extremely slowly growing inverse of Ackermann’s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to (n). We then extend the techniques used in these algorithms to a set of n circles. The resulting algorithm runs in optimal (n logn) time and (n) space., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Carlos Alegría: Research supported by MIUR Proj. “AHeAD” no 20174LF3T8. Justin Dallant: Research supported by French Community of Belgium via funding of a FRIA grant. Pablo Pérez-Lantero: Research supported by project DICYT 042332PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile). Carlos Seara: Corresponding author. Research supported by Spanish Ministry of Science and Innovation with project PID2019-104129GB-I00/AEI/10.13039/501100011033, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Shortest coordinated motions for square robots

  • Esteban, Guillermo
  • Halperin, Dan
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations (feasible in the sense that the two squares are interior disjoint), find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. In this paper we present an adaptation of the tools developed for the case of disks to the case of squares. We show that in certain aspects the case of squares is more complicated, requiring additional and more involved arguments over the case of disks., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. G. E. and R. I. S. were partially supported by projects PID2019-104129GB-I00 and PID2023-150725NBI00, funded by MICIU/AEI/10.13039/501100011033. Work by D. H. has been supported in part by the Israel Science Foundation (grant nos. 1736/19 and 2261/23), by NSF/US-Israel-BSF (grant no. 2019754), by the Blavatnik Computer Science Research Fund, and by the Shlomo Shmelzer Institute for Smart Transportation at Tel Aviv University., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On k-plane insertion into plane drawings

  • Katheder, Julia
  • Kindermann, Philipp
  • Klute, Fabian Maximilian|||0000-0002-7791-3604
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Rutter, Ignaz
We introduce the k-Plane Insertion into Plane drawing (k-PIP) problem: given a plane drawing of a planar graph G and a set F of edges, insert the edges in F into the drawing such that the resulting drawing is k-plane. In this paper, we show that the problem is NP-complete for every k = 1, even when G is biconnected and the set F of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that k = 1 and G is a triangulation., Julia Katheder: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 364468267. Fabian Klute: F. K. is supported by a “María Zambrano grant for attracting international talent” and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Ignaz Rutter: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 541433306., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Separating bichromatic point sets in the plane by restricted orientation convex hulls

  • Alegría Galicia, Carlos
  • Orden Martin, David
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
The version of record is available online at: http://dx.doi.org/10.1007/s10898-022-01238-9, We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and O be a set of k=2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of O for which the O-convex hull of R contains no points of B. For k=2 orthogonal lines we have the rectilinear convex hull. In optimal O(nlogn) time and O(n) space, n=|R|+|B|, we compute the set of rotation angles such that, after simultaneously rotating the lines of O around the origin in the same direction, the rectilinear convex hull of R contains no points of B. We generalize this result to the case where O is formed by k=2 lines with arbitrary orientations. In the counter-clockwise circular order of the lines of O, let ai be the angle required to clockwise rotate the ith line so it coincides with its successor. We solve the problem in this case in O(1/T·NlogN) time and O(1/T·N) space, where T=min{a1,…,ak} and N=max{k,|R|+|B|}. We finally consider the case in which O is formed by k=2 lines, one of the lines is fixed, and the second line rotates by an angle that goes from 0 to p. We show that this last case can also be solved in optimal O(nlogn) time and O(n) space, where n=|R|+|B|., Carlos Alegría: Research supported by MIUR Proj. “AHeAD” no 20174LF3T8. David Orden: Research supported by Project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACY, 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
Publicación Contribución de congreso (ConferenceOutput)

Shortest paths in portalgons

  • Löffler, M.
  • Ophelders, Tim
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Staals, Frank
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons., Tim Ophelders: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Rodrigo I. Silveira: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Center of maximum-sum matchings of bichromatic points

  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
© 2024 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Let R and B be two point sets in the plane with . Let be a perfect matching that matches points of R with points of B and maximizes , the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point o of the plane (the center of ) such that for all ., P. P-L. was partially supported by project DICYT 042332PL Vicerrector´ıa de Investigaci´on, Desarrollo e Innovaci´on USACH (Chile). C. S. was supported by Project PID2019-104129GB-I00/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación Artículo científico (JournalArticle)

Affine invariant triangulations

  • Bose, Prosenjit
  • Cano Vila, Pilar
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2021 Elsevier. 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 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 (1993) that uses the inverse of the covariance matrix of S to define an affine invariant norm, denoted , and an affine invariant triangulation, denoted . We revisit the -norm from a geometric perspective, and show that 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 such as being 1-tough, containing a perfect matching, and being a constant spanner of the complete geometric graph of S. We show that the -norm extends to a hierarchy of related geometric structures such as the minimum spanning tree, nearest neighbor graph, Gabriel graph, relative neighborhood graph, and higher order versions of these graphs. In addition, we provide different affine invariant sorting methods of a point set S and of the vertices of a polygon P that can be combined with known algorithms to obtain other affine invariant triangulation methods of S and of P. Our sorting methods provide a novel alternative to computing affine invariant geometric structures that are computationally simpler than using the -norm. In this work we focus on the theoretical part of affine invariant methods and as such do not provide experimental results., P.B. and P.C. were partially supported by NSERC. P.C. was supported by CONACyT and by the Fonds de la Recherche Scientifique-FNRS under Grant n° MISU F 6001 1. R.S. was supported by projects PID2019-104129GB-I00/ AEI/ 10.13039/ 501100011033 and Gen. Cat. 2017-SGR-1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

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

A new meta-module design for efficient reconfiguration of modular robots

  • Parada, Irene
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
This is a post-peer-review, pre-copyedit version of an article published in Autonomous Robots. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10514-021-09977-6, We propose a new meta-module design for two important classes of modular robots. The new metamodule is three-dimensional, robust and compact, improving on the previously proposed one. It applies to socalled “edge-hinged” modular robot units, such as MTRAN, SuperBot, SMORES, UBot, PolyBot and CKBot, as well as to so-called “central-point-hinged” modular robot units, which include Molecubes and Roombots. The new meta-module uses the rotational degrees of freedom of these two types of robot units in order to expand and contract, as to double or halve its length in each of the two directions of its three dimensions, therefore simulating the capabilities of Crystalline and Telecube robots. Furthermore, in the edge-hinged case we prove that the novel meta-module can also perform the scrunch, relax and transfer moves that are necessary in any tunnelingbased reconfiguration algorithm for expanding/contracting modular robots such as Crystalline and Telecube. This implies that the use of meta-meta-modules is unnecessary, and that currently existing efficient reconfiguration algorithms can be applied to a much larger set of modular robots than initially intended., 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. I.P. was supported by the Austrian Science Fund (FWF): W1230. V.S. and R.S. were supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. R.S. was also supported by MINECO through the Ram´on y Cajal program., Peer Reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación 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
Publicación 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
Publicación 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.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

  • Aichholzer, Oswin
  • García, Alfredo
  • Tejel, Javier
  • Vogtenhuber, Birgit
  • Weinberger, Alexandra
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Twisted ways to find plane structures in simple drawings of complete graphs

  • Aichholzer, Oswin
  • García, Alfredo
  • Tejel, Javier
  • Vogtenhuber, Birgit
  • Weinberger, Alexandra
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains [fórmula] pairwise disjoint edges and a plane cycle (and hence path) of length [fórmula]. Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Contribución de congreso (ConferenceOutput)

The complexity of geodesic spanners using Steiner points

  • de Berg, Sarita
  • Ophelders, Tim
  • Parada Muñoz, Irene María de
  • Staals, Frank
  • Wulms, Jules
A geometric t-spanner G on a set S of n point sites in a metric space P is a subgraph of the complete graph on S such that for every pair of sites p,q the distance in G is a most t times the distance d(p,q) in P. We call a connection between two sites a link. In some settings, such as when P is a simple polygon with m vertices and a link is a shortest path in P, links can consist of T(m) segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce k Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. Surprisingly, we show that Steiner points have only limited utility. For a spanner that uses k Steiner points, we provide an ¿(nm/k) lower bound on the worst-case complexity of any (3 - e)spanner, and an ¿(mn1/(t+1)/k1/(t+1)) lower bound on the worst-case complexity of any (t - e)spanner, for any constant e ¿ (0,1) and integer constant t = 2. These lower bounds hold in all settings. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a 3-spanner with a given maximum complexity using k Steiner points. On the positive side, for trees we show how to build a 2t-spanner that uses k Steiner points of complexity O(mn1/t/k1/t + nlog(n/k)), for any integer t = 1. We generalize this result to forests, and apply it to obtain a 2v2t-spanner in a simple polygon with total complexity O(mn1/t(logk)1+1/t/k1/t + nlog2 n). When a link in the spanner can be any path between two sites, we show how to improve the spanning ratio in a simple polygon to (2k + e), for any constant e ¿(0,2k), and how to build a 6t-spanner in a polygonal domain with the same complexity., Tim Ophelders: partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

New cyclic Kautz digraphs with optimal diameter

  • Böhmová, Katerina
  • Dalfó Simó, Cristina
  • Huemer, Clemens
We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' M C K ( d , l ) , and it is derived from the Kautz digraphs K ( d , l ) and from the so-called cyclic Kautz digraphs C K ( d , l ) . The cyclic Kautz digraphs C K ( d , l ) were defined as the digraphs whose vertices are labeled by all possible sequences a 1 … a l of length l , such that each character a i is chosen from an alphabet of d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a 1 ¿ a l . Their arcs are between vertices a 1 a 2 … a l and a 2 … a l a l + 1 , with a 1 ¿ a l and a 2 ¿ a l + 1 . Since C K ( d , l ) do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that M C K ( d , l ) are d -out-regular. Moreover, for t = 1 , we compute the number of vertices of the iterated line digraphs L t ( C K ( d , l ) ) ., The research of C. Dalfó has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under projects MTM2017-83271-R and PGC2018-095471-B-I00. The research of C. Huemer was supported by PID2019-104129GB-I00/AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922 ., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

ROADSTER: improved algorithms for subtrajectory clustering and map construction

  • Buchin, Kevin
  • Buchin, Maike
  • Gudmundsson, Joachim
  • Hendriks, Jorren
  • Hosseini Sereshgi, Erfan
  • Silveira, Rodrigo Ignacio
  • Sleijster, Jorrick
  • Staals, Frank
  • Wenk, Carola
The challenge of map construction involves creating a representation of a travel network using data from the paths traveled by entities within the network. Although numerous algorithms for constructing maps can effectively piece together the overall layout of a network, accurately capturing smaller details like the positions of intersections and turns tends to be more difficult. This difficulty is especially pronounced when the data is noisy or collected at irregular intervals. In this paper we present Roadster, a map construction system that combines efficient cluster computation and a sophisticated method to construct a map from a set of such clusters. First, edges are extracted by producing a number of subtrajectory clusters, of varying widths, which naturally correspond to paths in the network. Second, representative paths are extracted from the candidate clusters. The geometry of each representative path is improved in a process involving several stages, that leads to map edges. The rich information obtained from the clustering process is also used to compute map vertices, and to finally connect them using map edges. An experimental evaluation of Roadster, using vehicle and hiking GPS data, shows that the system can produce maps of higher quality than previous methods., We thank Roel Jacobs for the initial implementation of the bundling and map construction algorithms, and Vera Sacristán for her participation in an earlier version of this work. We also thank Songtao He for providing us with Roadrunner’s reconstructed map on Chicago (He et al., 2018). Yes. E. Hosseini Sereshgi and C. Wenk were partially supported by National Science Foundation, United States grants CCF-1637576 and CCF-2107434. R.I. Silveira was partially supported by MICINN through grant PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Coloraciones por entornos en jaulas de Moore

  • Hernando Martín, María del Carmen
  • Araujo Pardo, Gabriela
A k-coloring of a graph G is a k-partition = S1 Sk of V(G) into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices uv belonging to the same color Si, the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number, denoted by NL(G), is the minimum cardinality of a neighbor-locating coloring of G. In this paper we study the neighbor-locating coloring of graphs that are Moore cages., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Separating bichromatic point sets in the plane by restricted orientation convex hulls

  • Alegría Galicia, Carlos
  • Orden Martin, David
  • Seara Ojea, Carlos
  • Urrutia Galicia, Jorge
The version of record is available online at: http://dx.doi.org/10.1007/s10898-022-01238-9, We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and O be a set of k=2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of O for which the O-convex hull of R contains no points of B. For k=2 orthogonal lines we have the rectilinear convex hull. In optimal O(nlogn) time and O(n) space, n=|R|+|B|, we compute the set of rotation angles such that, after simultaneously rotating the lines of O around the origin in the same direction, the rectilinear convex hull of R contains no points of B. We generalize this result to the case where O is formed by k=2 lines with arbitrary orientations. In the counter-clockwise circular order of the lines of O, let ai be the angle required to clockwise rotate the ith line so it coincides with its successor. We solve the problem in this case in O(1/T·NlogN) time and O(1/T·N) space, where T=min{a1,…,ak} and N=max{k,|R|+|B|}. We finally consider the case in which O is formed by k=2 lines, one of the lines is fixed, and the second line rotates by an angle that goes from 0 to p. We show that this last case can also be solved in optimal O(nlogn) time and O(n) space, where n=|R|+|B|., Carlos Alegría: Research supported by MIUR Proj. “AHeAD” no 20174LF3T8. David Orden: Research supported by Project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACY, 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 (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Shortest coordinated motion for square robots

  • Esteban Pascual, Guillermo
  • Halperin, Dan
  • Ruíz, Víctor
  • Sacristán Adinolfi, Vera
  • Silveira, Rodrigo Ignacio
We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations, find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. We present an adaptation of the tools developed for the case of discs by Kirkpatrick and Liu [Characterizing minimum-length coordinated motions for two discs. Proceedings 28th CCCG, 252-259, 2016; CoRR abs/1607.04005, 2016.] to the case of squares. Certain aspects of the case of squares are more complicated, requiring additional and more involved arguments over the case of discs. Our contribution can serve as a basic component in optimizing the coordinated motion of two squares among obstacles, as well as for local planning in sampling-based algorithms, which are often used in practice, in the same setting., Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Geometric thickness of multigraphs is ¿R-Complete

  • Förster, Henry
  • Kindermann, Philipp
  • Miltzow, Tillmann
  • Parada Muñoz, Irene María de
  • Terziadis, Soeren
  • Vogtenhuber, Birgit
We say that a (multi)graph has geometric thickness t if there exists a straight-line drawing and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t. This problem was shown to be NP-hard for (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is -complete already for thickness 30. Moreover, our reduction shows that the problem is -complete for 4392-planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are -complete., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A new meta-module design for efficient reconfiguration of modular robots

  • Parada, Irene
  • Sacristán Adinolfi, Vera
  • Silveira, Rodrigo Ignacio
This is a post-peer-review, pre-copyedit version of an article published in Autonomous Robots. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10514-021-09977-6, We propose a new meta-module design for two important classes of modular robots. The new metamodule is three-dimensional, robust and compact, improving on the previously proposed one. It applies to socalled “edge-hinged” modular robot units, such as MTRAN, SuperBot, SMORES, UBot, PolyBot and CKBot, as well as to so-called “central-point-hinged” modular robot units, which include Molecubes and Roombots. The new meta-module uses the rotational degrees of freedom of these two types of robot units in order to expand and contract, as to double or halve its length in each of the two directions of its three dimensions, therefore simulating the capabilities of Crystalline and Telecube robots. Furthermore, in the edge-hinged case we prove that the novel meta-module can also perform the scrunch, relax and transfer moves that are necessary in any tunnelingbased reconfiguration algorithm for expanding/contracting modular robots such as Crystalline and Telecube. This implies that the use of meta-meta-modules is unnecessary, and that currently existing efficient reconfiguration algorithms can be applied to a much larger set of modular robots than initially intended., 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. I.P. was supported by the Austrian Science Fund (FWF): W1230. V.S. and R.S. were supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. R.S. was also supported by MINECO through the Ram´on y Cajal program., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
© 2023 Elsevier. 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 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 , which is a shortest path from s to t in the space; a weighted shortest vertex path , which is an any-angle shortest path; and a weighted shortest grid path , which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios , , , which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that in the worst case, and this is tight. As a corollary, for the weighted any-angle path we obtain the approximation result ., 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 also funded by an FPU of the Universidad de Alcalá., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
  • Tuttle, Tyler
Let ¿(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x,y ¿ S, where every geodesic disk containing x and y contains ¿(n) points of S. We establish upper and lower bounds for ¿(n), and show that n 5 +1 = ¿(n) = n 4 +1. We also show that there always exist two points x,y ¿ S such that every geodesic disk with x and y on its boundary contains at least 16 665 (n - 2) ˜ n-2 41.6 points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of n 3 +1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of n-2 two-colored version of the problem., G. E., D. O. and R. S. are partially supported by grants PID2019-104129GB-I00 and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. P. B. and T. T. are supported in part by NSERC., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Shortest paths in portalgons

  • Löffler, M.
  • Ophelders, Tim
  • Silveira, Rodrigo Ignacio
  • Staals, Frank
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons., Tim Ophelders: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Rodrigo I. Silveira: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles

  • Alegria, Carlos
  • Dallant, Justin
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull witharbitraryorientation for asetofsegmentsandcircles.Wedescribe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to 2p. We first consider a set of n segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal (n logn) time and O(na(n)) space, where a(n) is the extremely slowly growing inverse of Ackermann’s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to (n). We then extend the techniques used in these algorithms to a set of n circles. The resulting algorithm runs in optimal (n logn) time and (n) space., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Carlos Alegría: Research supported by MIUR Proj. “AHeAD” no 20174LF3T8. Justin Dallant: Research supported by French Community of Belgium via funding of a FRIA grant. Pablo Pérez-Lantero: Research supported by project DICYT 042332PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile). Carlos Seara: Corresponding author. Research supported by Spanish Ministry of Science and Innovation with project PID2019-104129GB-I00/AEI/10.13039/501100011033, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Center of maximum-sum matchings of bichromatic points

  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
© 2024 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Let R and B be two point sets in the plane with . Let be a perfect matching that matches points of R with points of B and maximizes , the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point o of the plane (the center of ) such that for all ., P. P-L. was partially supported by project DICYT 042332PL Vicerrector´ıa de Investigaci´on, Desarrollo e Innovaci´on USACH (Chile). C. S. was supported by Project PID2019-104129GB-I00/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The oriented chromatic number of the hexagonal grid is 6

  • Lozano Boixadors, Antoni
The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χo(F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H2, Bielak (2006) proved that 5 ≤χo(H2) ≤ 6. Here we close the gap by showing that χo(H2) ≥ 6., This research was supported by project PID2019-104129GB-I00, funded by MICIU/AEI/10.13039/501100011033, and by Universitat Politècnica de Catalunya under grant AGRUPS-2023., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Continuous mean distance of a weighted graph

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Silveira, Rodrigo Ignacio
We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances between all pairs of vertices. This parameter provides a natural measure of the compactness of the graph, and has been intensively studied, together with several variants, including its version for weighted graphs. The continuous analog of the (discrete) mean distance is the mean of the distances between all pairs of points on the edges of the graph. Despite being a very natural generalization, to the best of our knowledge this concept has been barely studied, since the jump from discrete to continuous implies having to deal with an infinite number of distances, something that increases the difficulty of the parameter. In this paper, we show that the continuous mean distance of a weighted graph can be computed in time roughly quadratic in the number of edges, by two different methods that apply fundamental concepts in discrete algorithms and computational geometry. We also present structural results that allow for a faster computation of this continuous parameter for several classes of weighted graphs. Finally, we study the relation between the (discrete) mean distance and its continuous counterpart, mainly focusing on the relevant question of convergence when iteratively subdividing the edges of the weighted graph., This work was supported by grants PID2019-104129GB-I00/ AEI/ 10.13039/501100011033, Gen. Cat. 2017SGR1640, and PID2019-103900GB-I00., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Rectilinear convex hull of points in 3D and applications

  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
  • Urrutia Galicia, Jorge
The version of record of this article, first published in Journal of global optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10898-024-01402-3, Let P be a set of n points in R3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal O(n log n) time and O(n) space algorithm to compute RCH(P). We also obtain an efficient O(n log2 n) time and O(n log n) space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate R3 around the Z-axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in R3. Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in R3., Pablo Pérez-Lantero: Partially supported by project DICYT 042332PL Vicerrectoría de Investigación Desarrollo e Innovación USACH (Chile). Carlos Seara: Partially supported by project PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Jorge Urrutia: Supported in part by SEP-CONACYT of México, Proyecto 80268, and by PAPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica, UNAM., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Dynamic embeddings of dynamic single-source upward planar graphs

  • van der Hoog, Ivor
  • Parada Muñoz, Irene María de
  • Rotenberg, Eva
A directed graph G is upward planar if it admits a planar embedding where each edge is y-monotone. Unlike planarity testing, upward planarity testing is NP-hard except in restricted cases, such as when the graph has the single-source property (i.e., each connected component has one source). In this paper, we present a dynamic data structure for maintaining an upward combinatorial embedding -¿E (G) of a single-source upward planar graph subject to edge deletions, edge contractions, directed edge insertions across a face, and single-source-preserving vertex splits through specified corners (i.e., the gaps between pairs of consecutive edges that share a vertex and a face). We furthermore support changes to the embedding -¿E (G) in the form of subgraph flips that mirror or slide the placement of a subgraph that is connected to the rest of the graph via at most two vertices. Updates that are incompatible with the current upward planar embedding are identified and rejected. All update operations are supported as long as the graph remains upward planar. In addition, we support queries that can tell whether two vertices can be connected with a directed edge while the graph remains single-source (we call these uplinkability queries). If a pair of vertices are not uplinkable, we facilitate one-flip-linkable queries: These point to a flip that makes them uplinkable, if any such flip exists. We dynamically maintain a linear-size data structure on G which supports incidence queries between a vertex and a face, and uplinkability queries for vertex pairs. We support all updates and queries in O(log2 n) worst-case time., This research was supported by Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic Network Analysis”. Ivor van der Hoog: This project has additionally received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Eva Rotenberg: This research was additionally supported by Carlsberg Foundation Young Researcher Fellowship CF21-0302 “Graph Algorithms with Geometric Applications”., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Shortest coordinated motions for square robots

  • Esteban, Guillermo
  • Halperin, Dan
  • Silveira, Rodrigo Ignacio
We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations (feasible in the sense that the two squares are interior disjoint), find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. In this paper we present an adaptation of the tools developed for the case of disks to the case of squares. We show that in certain aspects the case of squares is more complicated, requiring additional and more involved arguments over the case of disks., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. G. E. and R. I. S. were partially supported by projects PID2019-104129GB-I00 and PID2023-150725NBI00, funded by MICIU/AEI/10.13039/501100011033. Work by D. H. has been supported in part by the Israel Science Foundation (grant nos. 1736/19 and 2261/23), by NSF/US-Israel-BSF (grant no. 2019754), by the Blavatnik Computer Science Research Fund, and by the Shlomo Shmelzer Institute for Smart Transportation at Tel Aviv University., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

Edge-minimum saturated k-planar drawings

  • Chaplick, Steven
  • Klute, Fabian Maximilian
  • Parada Muñoz, Irene María de
  • Rollin, Jonathan
  • Ueckerdt, Torsten
F. Klute was supported by the Netherlands Organisation for Scientific Research (NWO) project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510. I. Parada was supported by the Margarita Salas Fellowship 2021UPC‐MS‐67392 funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). F. Klute and I. Parada were supported by grant PID2019104129GB‐I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On weighted sums of numbers of convex polygons in point sets

  • Huemer, Clemens
  • Oliveros, Deborah
  • Pérez Lantero, Pablo
  • Torra Clotet, Ferran
  • Vogtenhuber, Birgit
The version of record of this article, first published in Discrete & Computational Geometry, is available online at Publisher’s website: https://doi.org/10.1007/s00454-022-00395-8, Let S be a set of n points in general position in the plane, and let Xk,(S) be the number of convex k-gons with vertices in S that have exactly points of S in their interior. We prove several equalities for the numbers Xk,(S). This problem is related to the Erd¿os–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well., Research of C.H. was partially supported by project MTM2015-63791-R (MINECO/ FEDER), PID-2019-104129GB-I00/MCIN/AEI/10.13039/501100011033, and by project Gen. Cat. DGR 2017SGR1336. D.O. was partially supported by project PAPIIT IG100721 and CONACyT 282280. P. P-L. was partially supported by project DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Research of B.V. was partially supported by the Austrian Science Fund (FWF) within the collaborative DACH project Arrangements and Drawings as FWF Project I 3340-N35. We thank an anonymous referee for helpful comments. This project has been supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Graphs attaining the upper bound on the isolation number

  • Lemanska, Magdalena
  • Mora Giné, Mercè
  • Souto Salorio, María josé
A set D of vertices of a graph is isolating if the set of vertices not belonging to D or not having a neighbour in D is independent. The isolation number of a graph G, denoted by ¿(G), is the minimum cardinality of an isolating set. It is known that ¿(G) = n/3 if G is a connected graph of order n, n = 3, different from a cycle of order 5. Moreover, trees attaining this upper bound have been characterized. In this work we characterize all unicyclic and block graphs of order n such that ¿(G) = n/3., Partially supported by projects PID2020-113230RB-C21 and PID2019-104129GBI00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and Gen.Cat. DGR2021-SGR-00266., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

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

Affine invariant triangulations

  • Bose, Prosenjit
  • Cano Vila, Pilar
  • Silveira, Rodrigo Ignacio
© 2021 Elsevier. 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 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 (1993) that uses the inverse of the covariance matrix of S to define an affine invariant norm, denoted , and an affine invariant triangulation, denoted . We revisit the -norm from a geometric perspective, and show that 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 such as being 1-tough, containing a perfect matching, and being a constant spanner of the complete geometric graph of S. We show that the -norm extends to a hierarchy of related geometric structures such as the minimum spanning tree, nearest neighbor graph, Gabriel graph, relative neighborhood graph, and higher order versions of these graphs. In addition, we provide different affine invariant sorting methods of a point set S and of the vertices of a polygon P that can be combined with known algorithms to obtain other affine invariant triangulation methods of S and of P. Our sorting methods provide a novel alternative to computing affine invariant geometric structures that are computationally simpler than using the -norm. In this work we focus on the theoretical part of affine invariant methods and as such do not provide experimental results., P.B. and P.C. were partially supported by NSERC. P.C. was supported by CONACyT and by the Fonds de la Recherche Scientifique-FNRS under Grant n° MISU F 6001 1. R.S. was supported by projects PID2019-104129GB-I00/ AEI/ 10.13039/ 501100011033 and Gen. Cat. 2017-SGR-1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On k-plane insertion into plane drawings

  • Katheder, Julia
  • Kindermann, Philipp
  • Klute, Fabian Maximilian
  • Parada Muñoz, Irene María de
  • Rutter, Ignaz
We introduce the k-Plane Insertion into Plane drawing (k-PIP) problem: given a plane drawing of a planar graph G and a set F of edges, insert the edges in F into the drawing such that the resulting drawing is k-plane. In this paper, we show that the problem is NP-complete for every k = 1, even when G is biconnected and the set F of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that k = 1 and G is a triangulation., Julia Katheder: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 364468267. Fabian Klute: F. K. is supported by a “María Zambrano grant for attracting international talent” and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Ignaz Rutter: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 541433306., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Graph sampling for map comparison

  • Aguilar Larruy, Jordi
  • Buchin, Kevin
  • Buchin, Maike
  • Hosseini Sereshgi, Erfan
  • Silveira, Rodrigo Ignacio
  • Wenk, Carola
Comparing two road maps is a basic operation that arises in a variety of situations. A map comparison method that is commonly used, mainly in the context of comparing reconstructed maps to ground-truth maps, is based on graph sampling. The essential idea is to first compute a set of point samples on each map and then to match pairs of samples—one from each map—in a one-to-one fashion. For deciding whether two samples can be matched, different criteria, e.g., based on distance or orientation, can be used. The total number of matched pairs gives a measure of how similar the maps are. Since the work of Biagioni and Eriksson [11, 12], graph sampling methods have become widely used. However, there are different ways to implement each of the steps, which can lead to significant differences in the results. This means that conclusions drawn from different studies that seemingly use the same comparison method cannot necessarily be compared. In this work we present a unified approach to graph sampling for map comparison. We present the method in full generality, discussing the main decisions involved in its implementation. In particular, we point out the importance of the sampling method (GEO vs. TOPO) and that of the matching definition, discussing the main options used, and proposing alternatives for both key steps. We experimentally evaluate the different sampling and matching options considered on map datasets and reconstructed maps. Furthermore, we provide a code base and an interactive visualization tool to set a standard for future evaluations in the field of map construction and map comparison., E.H.S. and C.W. were partially supported by National Science Foundation grant CCF 1637576. R.I.S. was partially supported by project PID2019-104129GB-I00/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Computing largest minimum color-spanning intervals of imprecise points

  • Acharyya, Ankush
  • Keikha, Vahideh
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio
We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in time when , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard., A. Acharyya was supported by the DST-SERB grant number SRG/2022/002277. V. Keikha was supported by the CAS PPPLZ grant L100302301, and the institutional support RVO: 67985807. M. Saumell was supported by the Czech Science Foundation, grant number 23-04949X. R. Silveira was partially supported by grant PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033., Peer Reviewed, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

  • Alegría Galicia, Carlos
  • Orden Martin, David
  • Seara Ojea, Carlos
  • Urrutia Galicia, Jorge
This is a post-peer-review, pre-copyedit version of an article published in Journal of Global Optimization. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10898-020-00953-5, Let P be a set of n points in the plane. We compute the value of ¿¿[0,2p) for which the rectilinear convex hull of P, denoted by RHP(¿), has minimum (or maximum) area in optimal O(nlogn) time and O(n) space, improving the previous O(n2) bound. Let O be a set of k lines through the origin sorted by slope and let ai be the sizes of the 2k angles defined by pairs of two consecutive lines, i=1,…,2k. Let Ti=p-ai and T=min{Ti:i=1,…,2k}. We obtain: (1) Given a set O such that T=p2, we provide an algorithm to compute the O-convex hull of P in optimal O(nlogn) time and O(n) space; If T<p2, the time and space complexities are O(nTlogn) and O(nT) respectively. (2) Given a set O such that T=p2, we compute and maintain the boundary of the O¿-convex hull of P for ¿¿[0,2p) in O(knlogn) time and O(kn) space, or if T<p2, in O(knTlogn) time and O(knT) space. (3) Finally, given a set O such that T=p2, we compute, in O(knlogn) time and O(kn) space, the angle ¿¿[0,2p) such that the O¿-convex hull of P has minimum (or maximum) area over all ¿¿[0,2p)., Carlos Alegría: Research supported in part by UNAM Project PAEP, and by MIUR Proj. “AHeAD” No. 20174LF3T8. David Orden: Research supported by Projects MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE), and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACYT 80268, PAPPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica UNAM. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 734922., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

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 Mathematics, 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. Each pair of matched points p¿R and q¿B induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point., We thank the GeoGebra open source software and its developers [17]. S. B. was supported in part by NSF award CCF-1718994. D. F-P. was partially supported by PAPIIT IN120520 (UNAM, Mexico). C. H. and C. S. were partially supported by project MICINN 2020-2024 PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. P. P-L. was partially supported by projects DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñaloza, David
  • Huemer, Clemens
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
The version of record of this article, first published in Journal of Combinatorial Optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10878-023-01010-z, Given n > 0, let S ¿ [0,1]2 be a set of n points, chosen uniformly at random. 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 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 axis-aligned rectangles that cover exactly two points of S of the same color, and is strong in the sense that all of 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., Author Corujo was supported by grants from the Université Paris-Dauphine (France) and the ITI IRMIA++. Author Flores-Peñaloza was supported by project PAPIIT IN120520 (UNAM, Mexico). Author Huemer was supported by projects PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2021-SGR-00266. Author Pérez-Lantero was supported by projects CONICYT FONDECYT/Regular 1160543 (Chile), DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Author Seara was supported by project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/ 501100011033 and Gen. Cat. DGR 2021-SGR-00266., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

On the metric representation of the vertices of a graph

  • Mora Giné, Mercè
  • Puertas González, María Luz
The version of record is available online at: http://dx.doi.org/10.1007/s40840-023-01582-3, The metric representation of a vertex u in a connected graph G respect to an ordered vertex subset is the vector of distances . A vertex subset W is a resolving set of G if , for every with . Thus, a resolving set with n elements provides a set of metric representation vectors with cardinal equal to the order of the graph. In this paper, we address the reverse point of view; that is, we characterize the finite subsets that are realizable as the set of metric representation vectors of a graph G with respect to some resolving set W. We also explore the role that the strong product of paths plays in this context. Moreover, in the case , we characterize the sets that are uniquely realizable as the set of metric representation vectors of a graph G with respect to a resolving set W., This work was partially supported by the grants of the Spanish Ministry of Science and Innovation PID2021-123278OB-I00 and PID2019-104129GB-I00, both funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, and Gen. Cat. DGR 2021-SGR-00266., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
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 paper, 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 ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. 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 to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. 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 research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Flight Level Assignment Using Graph Coloring

  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Martínez Moraian, Alejandra|||0000-0002-8998-2121
  • Reyes Bardales, Rene D.
  • Orden Martín, David|||0000-0001-5403-8467
  • Marsá Maestre, Iván|||0000-0002-5529-2851
This paper models an air traffic optimization problem where, on the one hand, flight operators seek to minimize fuel consumption flying at optimal cruise levels and, on the other hand, air traffic managers aim to keep intersecting airways at as distant as possible flight levels. We study such a problem as a factorized optimization, which is addressed through a spectrum graph coloring model, evaluating the effect that safety constraints have on fuel consumption, and comparing different heuristic approaches for allocation., Ministerio de Ciencia e Innovación, European Union
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Separating bichromatic point sets in the plane by restricted orientation convex hulls

  • Alegría, Carlos
  • Orden Martín, David|||0000-0001-5403-8467
  • Seara, Carlos
  • Urrutia, Jorge
We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and O be a set of k >= 2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of O for which the O-convex hull of R contains no points of B. For k = 2 orthogonal lines we have the rectilinear convex hull. In optimal O (n log n) time and O(n) space, n = vertical bar R vertical bar + vertical bar B vertical bar. we compute the set of rotation angles such that, after simultaneously rotating the lines of O around the origin in the same direction, the rectilinear convex hull of R contains no points of B. We generalize this result to the case where O is formed by k >= 2 lines with arbitrary orientations. In the counter-clockwise circular order of the lines of O, let alpha(i) be the angle required to clockwise rotate the ith line so it coincides with its successor. We solve the problem in this case in O(1/Theta . N log N) time and O(1/Theta . N) space, where Theta = min {alpha(1), ..., alpha(k)} and N = max{k, vertical bar R vertical bar + vertical bar B vertical bar}. We finally consider the case in which O is formed by k = 2 lines, one of the lines is fixed, and the second line rotates by an angle that goes from O to pi. We show that this last case can also be solved in optimal O(n log n) time and O(n) space, where n = vertical bar R vertical bar + vertical bar B vertical bar., Ministerio de Ciencia e Innovación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Distributed Remote E-Voting System Based on Shamir's Secret Sharing Scheme

  • Tejedor Romero, Marino|||0000-0002-1679-0161
  • Orden Martín, David|||0000-0001-5403-8467
  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Junquera Sánchez, Javier|||0000-0002-4597-6539
  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
A number of e-voting systems have been proposed in the last decades, attracting the interest of the research community. The challenge is far from being fully addressed, especially for remote systems. In this work, we propose DiverSEC, a distributed, remote e-voting system based on Shamir secret sharing, operations in Galois field and mixnets, which enables end-to-end vote verification. Parties participate as nodes in the network, protecting their interests and ensuring process integrity due to the conflicting interests. The threat model is very conservative, not letting even the most privileged actors to compromise votes privacy or integrity. Security in depth is implemented, overlapping different mechanisms to offer guarantees even in the most adverse operating conditions. The main contributions of the resulting system are our proposal for secret-sharing among the political parties, which guarantees that no party can compromise the integrity of the ballot without being detected and identified in real time, and the computational and architectural scalability of the proposal, which make it easy to implement., Ministerio de Ciencia e Innovación, European Union
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo|||0000-0002-0751-7729
  • Orden Martín, David|||0000-0001-5403-8467
  • Silveira Isoba, 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: aweighted shortest path SPw(s, t), which is a shortest path from s to t in the space; aweighted shortest vertex path SVPw(s, t), which is an any-angle shortest path; and a weighted shortest grid path SGPw(s, t), which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios SGPw(s,t) SPw(s,t) , SVPw(s,t) SPw(s,t) , SGPw(s,t) SVPw(s,t) , which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that SGPw(s,t) √ SPw(s,t) = 2 3 ≈1.15 in the worst case, and this is tight. As a corollary, for the weighted any-angle path SVPw(s, t) we obtain the approximation result SVPw(s,t) SPw(s,t) ⪅ 1.15., European Commission, Agencia Estatal de Investigación, Universidad de Alcalá
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Analyzing larger sample sets with rapid methods: Incomplete-block designs with free-sorting and free-linking tasks

  • Ac-Pangan, Marlon
  • Tejedor Romero, Marino|||0000-0002-1679-0161
  • Swatko, Kyra
  • Orden Martín, David|||0000-0001-5403-8467
  • Lahne, Jacob
As rapid, holistic methods for similarity and description—such as sorting and projective mapping—have grown in popularity, a limiting factor is the number of samples that can be presented to subjects: more than 25 food samples decreases the quality and stability of results. While incomplete-block designs could address this, their use has not been developed for these holistic methods. In this paper we present an empirical investigation into the use of incomplete-block designs with free sorting and the newer free linking. We compare these two methods because while their results are comparable, the cognitive tasks are different, and thus their suitability for incomplete-block designs may differ. We evaluated the effects of incomplete-block designs in two studies. In Study 1, 20 subjects evaluated 6/10 chocolate bars by free linking in an incomplete-block design, with each subject completing 2 blocks; results were compared to a complete-block evaluation of the 10 bars by free sorting and free linking. In Study 2, a total of 90 subjects evaluated 62 terms from a chocolate flavor-wheel in 3 conditions (between subjects): free sorting with complete blocks (N = 30, all 62 terms) and free sorting (N = 30) or free linking (N = 30) with 3 incomplete blocks of 16/62 terms. We introduce a novel method to evaluate stability for the incomplete-block designs that we call “pairwise simulation.” From Study 1, we find that pairwise simulation provides adequate stability estimates and that, with sufficient pairwise cooccurrences, free linking with incomplete blocks produces results that are comparable to free sorting or linking with complete blocks. From Study 2, we demonstrate that free linking with incomplete blocks can produce high quality results from a large sample set, maintaining the increased discrimination capacity that marks free linking in general, and that with incomplete blocks, free linking is likely to be more stable than free sorting. This research demonstrates that incomplete-block designs can be used with free linking, and also provides a new, effective method through pairwise simulation for evaluating stability with incomplete-block designs, which cannot be resampled using standard bootstrapping approaches., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo|||0000-0002-0751-7729
  • Orden Martín, David|||0000-0001-5403-8467
  • Silveira, Rodrigo I.
  • Tuttle, Tyler
19th International Symposium on Algorithms and Data Structures (WADS 2025)., Let Π(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x, y ∈ S, where every geodesic disk containing x and y contains Π(n) points of S. We establish upper and lower bounds for Π(n), and show that ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +1. We also show that there always exist two points x, y ∈ S such that every geodesic disk with x and y on its boundary contains at least 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Aromatic evolution of red wine aged in oak vats and barrels. relationship between volatile compunds and sensory analysis

  • Pérez Magariño, Silvia
  • Cano Mozo, Estela
  • Bueno Herrera, Marta
  • Fernández Fernández, Encarnación
  • Orden Martín, David|||0000-0001-5403-8467
  • Albors, Clara
  • López, Lorena
  • Navascués, Eva
Background and goals In recent years, some wineries have started to use wooden vats again for fermentation and/or for the storage of wines because they have attractive advantages for wine quality; for example, the use of wooden vats for alcoholic and malolactic fermentation of red wines may enhance the varietal characteristics and increase the complexity of the wine. The goal of this work was to study the evolution of the volatile compounds during the aging of red wine in oak vats compared to oak barrels, and the correlation of volatile compounds with sensory characteristics after 12 months of aging. Methods and key findings The red wines were produced according to the usual winemaking process in the winery and aged for 12 months in new untoasted wooden vats, new barrels, one-year-old barrels, and two-year-old barrels for two consecutive vintages. Volatile composition and sensory analyses were carried out. Conclusions and significance The wines aged in new barrels had a greater loss of ethyl esters and acetates of alcohols, while those aged in vats maintained slightly higher concentrations of these compounds which are responsible for fruity and floral aromas. A strong correlation was found between the sensory data and the volatile composition of the wines aged for 12 months, clearly distinguishing the wines aged in vats from those aged in barrels. These wines were well discriminated by projective mapping sensory analysis, which is an effective and simple tool to differentiate wines., Centro para el Desarrollo Tecnológico e Industrial, Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Optimal channel assignment on dense Wi-Fi networks using Thermodynamic Threshold Accepting

  • Tejedor Romero, Marino|||0000-0002-1679-0161
  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Cruz Piris, Luis de la|||0000-0002-9570-2851
  • Herranz Oliveros, David|||0009-0009-0926-3986
  • Marsá Maestre, Iván|||0000-0002-5529-2851
Channel assignment in Wi-Fi 6 dense networks is a challenging problem which critically impacts the performance of WLAN communications. Although there have been many proposals in the area of IEEE 802.11 channel assignment, LCCS has emerged as the de facto standard for distributed channel selection. Notwithstanding, centralized optimizers overcome the performance of distributed channel assignment algorithms, so their study is of utmost importance. One of the most successful optimization proposals in the state-of-the-art for Wi-Fi 4 is based on simulated annealing (SA). However, SA presents a significant limitation: its parameters must be adjusted manually for each scenario, otherwise yielding suboptimal solutions. In this paper, we propose a new technique for channel assignment optimization of Wi-Fi dense networks, called Thermodynamic Threshold Accepting (TTA), including modifications inspired by Threshold Accepting (TA) and Thermodynamic Simulated Annealing (TSA). With respect to SA, TTA avoids manual tuning, being able to adapt to the specific setting automatically. We evaluate TTA in a dense Wi-Fi model and, compared to SA, we show that our approach reaches optimal results without requiring any prior fine-tuning. We also show that TTA is even able to slightly overcome the performance of an accurately calibrated SA optimizer for the same number of iterations., Agencia Estatal de Investigación, Junta de Comunidades de Castilla-La Mancha, Universidad de Alcalá
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Image-based evaluation of beers at an online Pint of Science festival using projective mapping, check-all-that-apply and acceptability

  • Orden Martín, David|||0000-0001-5403-8467
  • Fernández Fernández, Encarnación
  • Tejedor Romero, Marino|||0000-0002-1679-0161
A total of n = 67 untrained attendants at an outreach science festival, online because of the COVID-19 pandemic but usually held at bars, used pictures of the brand logos to evaluate eight beers among the most commonly consumed in Spain. Projective mapping, acceptability and check-all-that-apply (CATA) were used, in all cases leading to a clear picture of the consumers' opinion. For projective mapping the panel provided four clear groups, the first dimension replicating the acceptability outcome and the second dimension separating the national beers from the foreign one. For CATA the panel differentiated beers on the basis of 8 of the 10 attributes considered. The best- and worst-rated beers in acceptability were associated, respectively, with positive and negative emotions from CATA, the worst-rated one being the only beer of type Pilsener and the one with the least alcohol. Practical Applications Not many works combined the use of projective mapping, check-all-that-apply, and acceptability. This study contributes to a better understanding of how those three techniques complement each other to shed light on the consumers' preference about commercial beers, based on images of their logos. The results obtained would be helpful for beer manufacturers in order to interpret the perception of commercial beers in a large market like Spain. Furthermore, this study shows the appropriateness of two-way feedback between research and outreach activities., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

On the benefits of channel bonding in dense, decentralized Wi-Fi 4 networks

  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Orden Martín, David|||0000-0001-5403-8467
  • Fernández Melián, Susel|||0000-0002-1576-4340
  • Tejedor Romero, Marino|||0000-0002-1679-0161
Channel bonding is a technique first defined in the IEEE 802.11n standard to increase the throughput in wireless networks by means of using wider channels. In IEEE 802.11n (nowadays also known as Wi-Fi 4), it is possible to use 40 MHz channels instead of the classical 20 MHz channels. Although using channel bonding can increase the throughput, the classic 802.11 setting only allows for two orthogonal channels in the 2.4 GHz frequency band, which is not enough for proper channel assignment in dense settings. For that reason, it is commonly accepted that channel bonding is not suitable for this frequency band. However, to the best of our knowledge, there is not any accurate study that deals with this issue thoroughly. In this work, we study in depth the effect of channel bonding in Wi-Fi 4 dense, decentralized networks operating in the 2.4 GHz frequency band. We confirm the negative effect of using channel bonding in the 2.4 GHz frequency band with 11 channels which are 20 MHz wide (as in North America), but we also show that when there are 13 or more channels at hand (as in many other parts of the world, including Europe and Japan), the use of channel bonding yields consistent throughput improvements. For that reason, we claim that the common assumption of not considering channel bonding in the 2.4 GHz band should be revised., Junta de Comunidades de Castilla-La Mancha, Universidad de Alcalá, Agencia Estatal de Investigación, European Commission
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

The free-linking task: a graph-inspired method for generating non-disjoint similarity data with food products

  • Lahne, Jacob
  • Phetxumphou, Katherine
  • Tejedor Romero, Marino|||0000-0002-1679-0161
  • Orden Martín, David|||0000-0001-5403-8467
"Free sorting", in which subjects are asked to sort a set of items into groups of "most similar" items, is increasingly popular as a technique for profiling sets of foods. However, free sorting implies an unrealistic model of sample similarity: that similarity is purely binary (is/is not similar) and that similarity is fully transitive (similarities {A, B} and {B, C} imply {A, C}). This paper proposes a new method of rapid similarity testing -- the "free-linking" task -- that solves both problems: in free linking, subjects draw a similarity graph in which they connect pairs of samples with a line if they are similar, according to the subject s individual criteria. This simple task provides a more realistic model of similarity which allows degrees of similarity through the graph distance metric and does not require transitive similarity. In two pilot studies with spice blends (10 samples, 58 subjects) and chocolate bars (10 samples, 63 subjects), free linking and free sorting are evaluated and compared using DISTATIS, RVb, and the graph parameters degree, transitivity, and connectivity; subjects also indicated their preferences and ease-of-use for the tasks. In both studies, the first two dimensions of the DISTATIS consensus were highly comparable across tasks; however, free linking provided more discrimination in dimensions three and four. RVb stability was equivalent for the two methods. Graph statistics indicated that free linking had greater discrimination power: on average subjects made similarity groupings with lower degree, lower transitivity, and higher connectivity for free linking in both studies. However, subjects did overall find free sorting easier and liked it more, indicating a higher cognitive difficulty of free linking. The free-linking task, therefore, provides more robust, realistic similarity maps at the cost of higher panelist effort, and should prove a valuable alternative for rapid sensory assessment of product sets., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Check-all-that-apply and storyworld possible selves: what consumer research methods can do for the study of narrative engagement

  • Martínez Martínez, María Ángeles|||0000-0001-6473-1249
  • Orden Martín, David|||0000-0001-5403-8467
  • Fernández Fernández, Encarnación
The empirical study of literary experiences affords the opportunity to investigate the extent to which the interpretations of literary critics may coincide with the meaning construction operations of flesh-and-blood readers. The present study explores the analytical potential of a statistics-based Check-all-that-apply (CATA) methodology, traditionally used in consumer research, in the study of real reader response. To this purpose, an online questionnaire designed along CATA lines is used to investigate the emergence of storyworld possible selves during narrative interaction with the graphic short story "City" (Wasco, 2015). The findings are compared to those of two previous studies of this short story, one literary (Herman & Vervaeck, 2019) and the other empirical (Martínez & Herman, 2020), and suggest that a CATA methodology can enlighten aspects of readerly response not previously addressed, particularly regarding the idiosyncratic construction of the main character in ways relevant to individual readers" construction of themselves., Agencia Estatal de Investigación, Universidad de Alcalá
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Channel Selection in Uncoordinated IEEE 802.11 Networks Using Graph Coloring

  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Hoz de la Hoz, Enrique de la|||0000-0003-4837-3837
  • Orden Martín, David|||0000-0001-5403-8467
  • Herranz Oliveros, David|||0009-0009-0926-3986
One of the big challenges in decentralized Wi-Fi networks is how to select channels for the different access points (APs) and their associated stations (STAs) in order to minimize interference and hence maximize throughput. Interestingly enough, de facto standards in terms of uncoordinated channel selection are quite simple, and in many cases result in fairly suboptimal channel allocations. Here, we explore how graph coloring can be used to evaluate and inform decisions on Wi-Fi channel selection in uncoordinated settings. Graph coloring, in its most basic form, is a classic mathematical problem where colors have to be assigned to nodes in a graph while avoiding assigning the same color to adjacent nodes. In this paper, we modeled Wi-Fi uncoordinated channel selection as a graph coloring problem and evaluated the performance of different uncoordinated channel selection techniques in a set of representative scenarios of residential buildings. The results confirm some of the widely accepted consensus regarding uncoordinated channel selection but also provide some new insights. For instance, in some settings, it would be better to delegate the decision on which channel to use to transmit the STAs, rather than having the AP make the decision on its own, which is the usual way., Ministerio de Ciencia e Innovación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

IEEE 802.11 graph models

  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Cruz Piris, Luis De La|||0000-0002-9570-2851
  • Orden Martín, David|||0000-0001-5403-8467
  • Tejedor Romero, Marino|||0000-0002-1679-0161
There are several recent research lines addressing Wi-Fi network planning and optimization, both in terms of channel assignment and access point deployment. The problem with these works is that evaluation is usually performed with specific and closed models regarding signal propagation, throughput computation, and utility definition. Also, many of the models in the literature make assumptions about the role of wireless stations, or the co-channel interference, which -while being valid in the context of a single research work- makes very difficult to compare different approaches, to re-use concepts from previous mechanisms to create new ones, or to generalize mechanisms to other scenarios. This makes the different research lines in Wi-Fi network planning and optimization progress in an isolated manner. This paper aims to address such a recurring problem by proposing a graph-based generic model for Wi-Fi utility computation in network planning scenarios, as well as providing a collection of scenario graphs which may be used to benchmark different planning and optimization approaches. Experiments are conducted to show the validity of the model and the significance of its features, along with its extensibility to other scenarios., Agencia Estatal de Investigación, Junta de Comunidades de Castilla-La Mancha, Universidad de Alcalá, European Commission