DOI: 10.1007/978-3-319-22177-9

Date of publication: 2015-08-17

Abstract:

We consider stabbing regions for a set S of n line segments in the plane, that is, regions in the plane that contain exactly one endpoint of each segment of S. Concretely, we provide efficient algorithms for reporting all combinatorially different stabbing regions for S for regions that can be described as the intersection of axis-parallel halfplanes; these are halfplanes, strips, quadrants, 3-sided rectangles, and rectangles. The running times are O(n) (for the halfplane case), O(n log n) (for strips, quadrants, and 3-sided rectangles), and O(n2 log n) (for rectangles).]]>

Spanish Meeting on Computational Geometry

p. 112-115

Presentation's date: 2015-07-03

Abstract:

We study the problem of computing stabbing circles of a set S of n line segments in the plane. We provide efficient algorithms: (i) to compute a representation of all the combinatorially different stabbing circles for S, and the ones with maximum and minimum radius, in O(n^2) time and space; (ii) to decide if there exists a stabbing circle for a set of parallel segments in O(n log^2 n) time and O(n) space.]]>

Spanish Meeting on Computational Geometry

p. 93-96

Presentation's date: 2015-07-03

Abstract:

We consider stabbing regions for a set S of n line segments in the plane, defined as regions that contain exactly one endpoint of each segment of S. We provide efficient algorithms that report all combinatorially different stabbing regions for S when the regions are described as the intersection of isothetic halfplanes: halfplanes, strips, quadrants, 3-sided rectangles, and rectangles. The running times are O(n) (for the halfplane case), O(n log n) (for strips, quadrants, and 3-sided rectangles), and O(n^2 log n) (for rectangles)]]>

Spanish Meeting on Computational Geometry

p. 5-8

Presentation's date: 2015-07-01

Abstract:

A natural relaxation for problems that have no solution for plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, there can be at most one crossing per edge. In this work, we study this relaxation for Hamiltonian alternating cycles and paths. Thus, it is well-known that one cannot always draw a plane Hamiltonian alternating cycle, even on a bicolored point set in convex position, whilst we prove that allowing the cycle to be 1-plane, it can always be found, on a point set in general position, in O(n^2) time and space. We also restrict ourselves to bicolored point sets in convex position obtaining a remarkable variety of results. Among them, we show that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and we compute Hamiltonian alternating cycles and paths with minimum number of crossings in, respectively, O(n) and O(n^2) time and space.]]>

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.]]>