Abstract:

The unifying focus of this project is computational geometry, with emphasis on both combinatorial and algorithmic problems on the relationship between combinatorial graphs and their geometric embeddings. This disciplinary framework is inserted into a wider one, namely discrete and algorithmic mathematics. Its major development in recent times is due to its association with computer and communication technologies. This is why it still requires an intense and sustained research effort. With this project we want to channel the general research activity of the group, with its multiplicity of cooperative working lines, while at the same time intensifying work on a specific topic: the interaction between combinatorial and geometric graphs. Simultaneously, we intend to consolidate the direction initiated in the previous project (MTM2012-30951/FEDER) intensifying the identification and study of problems arising from application areas. Although one cannot ignore the fact that our research is of theoretical kind, we cannot ignore either that many of the problems that computational geometry studies arise from its many applications. We have structured our proposal in three lines of work of a fundamental nature: A1. Domination in combinatorial graphs, A2. Domination and coverings in geometric graphs, A3. Geometric embedding of combinatorial graphs, plus another two, more oriented towards applications: B1. Modular robotic system reconfiguration, B2. Geometric algorithms for geographic information, Regarding the foundations of theoretical type, the research lines we propose seek to delve into the study of combinatorial properties of graphs (A1) whose transposition to geometric graphs (A2) is of great interest for the research community in combinatorial and algorithmic geometry: domination, location, covering... This relationship between properties of combinatorial graphs and those of geometric graphs is also evident in the crucial fact that is reflected in A3: on the one hand, the study of combinatorial properties of graphs is eased by the study of their embeddings in the plane and, conversely, the study of sets of points -in the plane and in higher dimension- is eased by studying the graphs they determine. As for the applications, the three subjects that this project aims to emphasize are linked to the previous subjects because the algorithms of B1 rely on properties of regular graphs and minimum spanning trees, and some of the problems of B2 are directly related to visibility problems on terrains. Main objective: scientific achievements. The natural objective of this project is to obtain as complete and advanced results as possible in the study of the algorithmic-geometric problems described above. Additional objectives: in parallel with the main objective, we have two other complementary goals which are also natural in a project of this nature: maintaining the international projection of the group, and maintaining our efforts into training young researchers.]]>

Abstract:

The present project aims to articulate the group's overall research activity, maintaining multiple cooperative lines of work, but at the same time enhancing a specific topic and introducing a new more exploratory aspect. The unifying bond is computational geometry, with emphasis on algorithmic problems related to the capture, identification or optimization of geometric shape, understood in a broad sense. We propose to study both the corresponding theoretical foundations, and initiate further exploration more targeted to applications, one on reconfigurable modular robots, another revolving around the type of discriminatory analysis proper to operational research. The scientific results obtained will be combined with the training of new researchers, and maintaining the group's presence and projection in the state and international arenas. This project is conceived as a continuation of MTM2009-07242, but with several significant differences, due both to current trends in the international research community and to some small changes in the composition of the group. We have grouped the issues to be investigated into two blocks, one more theoretical and the other more oriented towards applications; however, let us be clear that the latter is also quite theoretical. We proceed to briefly outline the contents of these blocks, by specifying some particular issues: A. Theory of discrete geometric shape: foundations, algorithms, optimization 1. Algorithmic study of families of symmetric polytopes and operations on them: Study of structural properties of discrete families of polytopes constructed from the spectrum of graphs with symmetry, and new operations on them, such as the tensor product. 2. Discrete sets: Algorithms for increasing the connectivity for simultaneous biplane graphs and problems of constructing compatible graphs sharing a minimum number of edges. Characterization of sets that support graphs with connectivity or regularity 4 or 5, but which may increase in two layers. Study of the rectilinear convex hull (RCH) of sets of points and objects: optimization of different parameters of the RCH, calculation of the non-oriented RCH optimizing area, perimeter, number of connected components, etc.; algorithmic applications to classification problems and grouping of geometric objects. 3. Location and dominance of vertices in combinatorial graphs: Study of various parameters related to the notion of convexity in graphs, such as location and domination. Upper and lower bounds of these parameters in terms of order and diameter. Relationship between the various parameters. Study of these parameters in some specific families of graphs. B. The road towards applications: two concrete aspects of the use of shapes 1.Reconfiguration of modular robotic systems: Efficient distributed algorithms based on local rules for solving tasks of self-organization and reconfiguration of lattice-based modular robotic systems. Generalization to a generic conceptual model that can be applied to most real and potentially existing prototypes. Proof of the correctness of the rule sets, the efficiency of the resulting algorithms, and of the connectedness of the reconfiguration space. Development of a simulator. Presentation and analysis of experimental results. 2.Geometric outlier detection: A study of the application of classical tools and algorithms of computational geometry in disciplines such as health, education and marketing, which must process large amounts of data that can be described geometrically. In particular, we will focus on the detection of data that are outliers according to some chosen criterion, and on the reliable estimation of missing values.]]>