Pasar al contenido principal

COMBINATORIA Y COMPLEJIDAD DE ESTRUCTURAS GEOMETRICAS DISCRETAS

MTM2017-83750-P

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2017
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE CANTABRIA

Resultados relacionados

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

RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

The complete classification of empty lattice 4-simplices

  • Iglesias Valiño, Óscar
  • Santos, Francisco
©2018 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/bync-nd/4.0/. This version of the article has been accepted for publication in Electronic Notes in Discrete Mathematics. The Version of Record is available online at https://doi.org/10.1016/j.endm.2018.06.027, [Abstract]: In previous work we classified all empty 4-simplices of width at least three. We here classify those of width two. There are 2 two-parameter families that project to the second dilation of a unimodular triangle, 29+23 one-parameter families of them that project to hollow 3-polytopes, and 2282 individual ones that do not., Supported by grants MTM2014-54207-P (both authors) and BES-2015-073128 (O. Iglesias) of the Spanish Ministry of Economy and Competitiveness. F. Santos is also supported by the Einstein Foundation Berlin, Einstein Foundation Berlin; EVF-2015-230
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

The complete classification of empty lattice 4-simplices

  • Iglesias Valiño, Óscar
  • Santos, Francisco
Accepted version for: Óscar Iglesias-Valiño, Francisco Santos, The complete classification of empty lattice 4-simplices. Rev. Mat. Iberoam. 37 (2021), no. 6, pp. 2399–2432. DOI 10.4171/RMI/1268, [Abstract]: An empty simplex is a lattice simplex with only its vertices as lattice points. Their classification in dimension three was completed by G. White in 1964. In 1988, S. Mori, D. R. Morrison, and I. Morrison started the task in dimension four, with their motivation coming from the close relationship between empty simplices and terminal quotient singularities. They conjectured a classification of empty simplices of prime volume, modulo finitely many exceptions. Their conjecture was proved by Sankaran (1990) with a simplified proof by Bober (2009). The same classification was claimed by Barile et al. in 2011 for simplices of non-prime volume, but this statement was proved wrong by Blanco et al. (2016+). In this article, we complete the classification of 4-dimensional empty simplices. In doing so, we correct and complete the classification by Barile et al., and we also compute all the finitely many exceptions, by first proving an upper bound for their volume. The whole classification has: 1) One 3-parameter family, consisting of simplices of width equal to one. 2) Two 2-parameter families (the one in Mori et al., plus a second new one). 3) Forty-six 1-parameter families (the 29 in Mori et al., plus 17 new ones). 4) 2461 individual simplices not belonging to the above families, with (normalized) volumes ranging between 24 and 419. We characterize the infinite families of empty simplices in terms of the lower dimensional point configurations that they project to, with techniques that can potentially be applied to higher dimensions and other classes of lattice polytopes., Supported by grants MTM2014-54207-P and MTM2017-83750-P (both authors) and BES-2015-073128 (O.Iglesias) of the Spanish Ministry of Economy and Competitiveness. F. Santos is also supported by the Einstein Foundation Berlin under grant EVF-2015-230., Einstein Foundation Berlin; EVF-2015-230
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Classification of empty lattice 4-simplices of width larger than 2

  • Iglesias Valiño, Óscar
  • Santos, Francisco
©2017 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/bync-nd/4.0/. This version of the article has been accepted for publication in Electronic Notes in Discrete Mathematics. The Version of Record is available online at https://doi.org/10.1016/j.endm.2017.07.019, [Abstract]: Combining an upper bound on the volume of empty lattice 4-simplices of large width with a computer enumeration we prove the following conjecture of Haase and Ziegler (2000): Except for 179 classes, of determinant at most 179, all empty 4-simplices have width one or two with respect to some integer functional., Supported by grants MTM2014-54207-P (both authors) and BES-2015-073128 (O. Iglesias) of the Spanish Ministry of Economy and Competitiveness. F. Santos is also supported by the Einstein Foundation Berlin.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

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

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

  • Alegría Galicia, Carlos
  • Orden Martín, David|||0000-0001-5403-8467
  • Seara, Carlos
  • Urrutia, Jorge
Let P beasetofn points in the plane. We compute the value of θ ∈[0,2π) for which the rectilinear convex hull of P, denoted by RHP(θ), has minimum (or maximum) area in optimal O(n logn) 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 αi be the sizes of the 2k angles defined by pairs of two consecutive lines, i = 1,...,2k.Let i = π − αi and =min{ i : i =1,...,2k}.Weobtain:(1)Givenaset O suchthat ≥ π 2 ,weprovidean algorithm to compute the O-convex hull of P in optimal O(n logn) time and O(n) space; If <π 2 , the time and space complexities are O( n logn) and O( n) respectively. (2) Given a set O such that ≥ π 2 , we compute and maintain the boundary of the Oθ-convex hull of P for θ ∈[0,2π)in O(knlogn)time and O(kn)space, or if <π 2 ,inO(k n logn)time and O(k n) space. (3) Finally, given a set O such that ≥ π 2 , we compute, in O(knlogn) time and O(kn) space, the angle θ ∈[0,2π)such that the Oθ-convex hull of P has minimum (or maximum) area over all θ ∈[0,2π)., Agencia Estatal de Investigación, European Commission
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Testing SensoGraph, a geometric approach for fast sensory evaluation

  • Orden Martín, David|||0000-0001-5403-8467
  • Fernández Fernández, Encarnación
  • Rodríguez Nogales, José M.
  • Vila Crespo, Josefina
This paper introduces SensoGraph, a novel approach for fast sensory evaluation using two-dimensional geometric techniques. In the tasting sessions, the assessors follow their own criteria to place samples on a tablecloth, according to the similarity between samples. In order to analyse the data collected, first a geometric clustering is performed to each tablecloth, extracting connections between the samples. Then, these connections are used to construct a global similarity matrix. Finally, a graph drawing algorithm is used to obtain a 2D consensus graphic, which reflects the global opinion of the panel by (1) positioning closer those samples that have been globally perceived as similar and (2) showing the strength of the connections between samples. The proposal is validated by performing four tasting sessions, with three types of panels tasting different wines, and by developing a new software to implement the proposed techniques. The results obtained show that the graphics provide similar positionings of the samples as the consensus maps obtained by multiple factor analysis (MFA), further providing extra information about connections between samples, not present in any previous method. The main conclusion is that the use of geometric techniques provides information complementary to MFA, and of a different type. Finally, the method proposed is computationally able to manage a significantly larger number of assessors than MFA, which can be useful for the comparison of pictures by a huge number of consumers, via the Internet., Ministerio de Economía, Comercio y Empresa, Universidad de Alcalá, European Commision
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

  • González Aguilar, Hernán
  • Orden Martín, David|||0000-0001-5403-8467
  • Pérez Lantero, Pablo
  • Rappaport, David
  • Seara, Carlos
  • Tejel, Javier
  • Urrutia, Jorge
Let P be a set of n points in the plane. We consider a variation of the classical Erdos-Szekeres problem, presenting efficient algorithms with O(n(3)) running time and O(n(2)) 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., Ministerio de Ciencia e Innovación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction

  • Orden Martín, David|||0000-0001-5403-8467
  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Hoz de la Hoz, Enrique de la|||0000-0003-4837-3837
  • Álvarez Suárez, Ana
The present work deals with the problem of efficiently assigning Wi-Fi channels in a real-world scenario, the Polytechnic School of the University of Alcala. We first use proximity graphs to model the whole problem as an instance of spectrum graph coloring, we further obtain a simplified model using edge contraction, and we finally use simulated annealing to look for a coloring which optimizes the network throughput. As the main result, we show that the solutions we obtain outperform the de facto standard for Wi-Fi channel assignment, both in terms of network throughput and of computation time., Ministerio de Economía, Comercio y Empresa, Ministerio de Ciencia, European Union
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Nonlinear Negotiation Approaches for Complex-Network Optimization: A Study Inspired by Wi-Fi Channel Assignment

  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Hoz de la Hoz, Enrique de la|||0000-0003-4837-3837
  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Orden Martín, David|||0000-0001-5403-8467
  • Klein, Mark
At the present time, Wi-Fi networks are everywhere. They operate in unlicensed radio-frequency spectrum bands (divided in channels), which are highly congested. The purpose of this paper is to tackle the problem of channel assignment in Wi-Fi networks. To this end, we have modeled the networks as multilayer graphs, in a way that frequency channel assignment becomes a graph coloring problem. For a high number and variety of scenarios, we have solved the problem with two different automated negotiation techniques: a hill-climbing mediated negotiation and a simulated annealing mediated negotiation. As an upper bound reference for the performance of these two techniques, we have also solved the problem using a particle swarm optimizer. Results show that the annealer negotiator behaves as the best choice because it is able to obtain even better results than the particle swarm optimizer in the most complex scenarios under study, with running times one order of magnitude below. Moreover, we study how different properties of the network layout affect to the performance gain that the annealer is able to obtain with respect to the particle swarm optimizer. Finally, we show how the different strategic behavior of the participants affects the results., Ministerio de Economía y Competitividad, Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

REACT: reactive resilience for critical infrastructures using graph-coloring techniques

  • Marsá Maestre, Iván|||0000-0002-5529-2851
  • Giménez Guzmán, José Manuel|||0000-0002-1645-8476
  • Orden Martín, David|||0000-0001-5403-8467
  • Hoz de la Hoz, Enrique de la|||0000-0003-4837-3837
  • Klein, Mark
Nowadays society is more and more dependent on critical infrastructures. Critical network infrastructures (CNI) are communication networks whose disruption can create a severe impact. In this paper we propose REACT, a distributed framework for reactive network resilience, which allows networks to reconfigure themselves in the event of a security incidents so that the risk of further damage is mitigated. Our framework takes advantage of a risk model based on multilayer networks, as well as a graph-coloring problem conversion, to identify new, more resilient configurations for networks in the event of an attack. We propose two different solution approaches, and evaluate them from two different perspectives, with a number of centralized optimization techniques. Experiments show that our approaches outperform the reference approaches in terms of risk mitigation and performance., Ministerio de Economía y Competitividad, Universidad de Alcalá, Agencia Estatal de Investigación, European Commission
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Optimizing generalized kernels of polygons

  • Martínez Moraian, Alejandra|||0000-0002-8998-2121
  • Orden Martín, David|||0000-0001-5403-8467
  • Palios, Leonidas
  • Seara, Carlos
  • Żyliński, Pawel
Let O beasetofk orientations in the plane, and let P be a simple polygon in the plane. Given two points p,q inside P, we say that p O-sees q if there is an O-staircase contained in P that connects p and q.TheO-Kernel of the polygon P, denoted by O-Kernel(P), is the subset of points of P which O-see all the other points in P. This work initiates the study of the computation and maintenance of O-Kernel(P) as we rotate the set O by an angle θ, denoted by O-Kernelθ(P). In particular, we consider the case when the set O is formed by either one or two orthogonal orientations, O ={0◦} or O ={0◦,90◦}. For these cases and P being a simple polygon, we design efficient algorithms for computing the O-Kernelθ(P) while θ varies in [−π 2 , π 2 ), obtaining: (i) the intervals of angle θ where O-Kernelθ(P) is not empty, (ii) a value of angle θ where O-Kernelθ(P) optimizes area or perimeter. Further, we show how the algorithms can be improved when P is a simple orthogonal polygon. In addition, our results are extended to the case of a set O ={α1,...,αk}., Agencia Estatal de Investigación, European Commission
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Cellular morphogenesis of three-dimensional tensegrity structures

  • Aloui, Omar
  • Flores, Jessica
  • Orden Martín, David|||0000-0001-5403-8467
  • Rhode Barbarigos, Landolf
The topology and form finding of tensegrity structures have been studied extensively since the introduction of the tensegrity concept. However, most of these studies address topology and form separately, where the former represented a research focus of rigidity theory and graph theory, while the latter attracted the attention of structural engineers. In this paper, a biomimetic approach for the combined topology and form finding of spatial tensegrity systems is introduced. Tensegrity cells, elementary infinitesimally rigid self-stressed structures that have been proven to compose any tensegrity, are used to generate more complex tensegrity structures through the morphogenesis mechanisms of adhesion and fusion. A methodology for constructing a basis to describe the self-stress space is also provided. Through the definition of self-stress, the cellular morphogenesis method can integrate design considerations, such as a desired shape or number of nodes and members, providing great flexibility and control over the tensegrity structure generated., Agencia Estatal de Investigación, European Commission
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Estimation of the spatio-temporal wave grouping properties by using multidimensional discrete and spline methods

  • Nieto Borge, José Carlos|||0000-0002-3158-3822
  • Alcázar Arribas, Juan Gerardo|||0000-0002-1665-9710
  • Orden Martín, David|||0000-0001-5403-8467
  • Marazuela Reca, Sara
  • Rodríguez, Gerardo
Wave groups can be detected and studied by using the wave envelope. So far, the method used to compute the wave envelope employs the Riesz transform. However, such a technique always produces symmetric envelopes, which is only realistic in the case of linear waves. In this paper we present a new method to compute the wave envelope providing more realistic results. In particular, the method allows to detect non-symmetry in the wave envelope, something useful, for instance, when detecting groups of high waves. The method computes first the local maxima and minima of the sea surface, and then determines the wave envelope by combining discrete methods, namely the use of the Delaunay triangulation, and tensor-product splines. The proposed method has been applied to simulated wave fields, and also to wave elevations data measured by an X-band radar. The obtained results correctly reproduce the behavior of the simulated waves., Ministerio de Economía y Competitividad, Agencia Estatal de Investigación, European Commission