URRUTIA GALICIA , Jorge (Coordinador)

Let S be a set of n points in Rd in general position. A set H of k-flats is called an mk-stabber of S if the relative interior of any m-simplex with vertices in S is intersected by at least one element of H. In this paper we give lower and upper bounds on the size of minimum mk-stabbers of point sets in Rd. We study mainly mk-stabbers in the...

Let P and F be sets of n ≥ 2 and m ≥ 2 points in the plane, respectively, so that P∪F is in general position. We study the problem of finding the minimum angle α ∈ [2π/m, 2π] such that one can install at each point of F a stationary rotating floodlight with illumination angle α, initially oriented in a suitable direction, in such a way that, at...

Abstract Voronoi diagrams are a unifying framework that covers many types of concrete Voronoi diagrams. This talk reports on the state of the art, including recent progress.

A simple topological graph T = (V (T ), E(T )) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G...

Let f(n) be a function and L be a graph. Denote by RT(n, L, f(n)) the maximum number of edges of an L-free graph on n vertices with independence number less than f(n). Erdos and Sós asked if RT (n, K5, c√ n) = o (n2) for some constant c. We answer this question by proving the stronger RT(n, K5, o (√n log n)) = o(n2). It is known that RT (n, K5,...

Based on some recent modelling considerations in location theory we call for study of three CG constructs of Voronoi type that seem not to have been studied much before.

It is well known that, given n red points and n blue points on a circle, it is not always possible to find a plane geometric Hamiltonian alternating path. In this work we prove that if we relax the constraint on the path from being plane to being 1-plane, then the problem always has a solution, and even a Hamiltonian alternating cycle can be...

Ministerio de Economía y Competitividad

A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled without overlaps by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d=2, triangular k-reptiles exist for many values of k and they have been completely characterized by Snover, Waiveris, and Williams. On the...

Although the exact counting and enumeration of polyominoes remain challenging open problems, several positive results were achieved for special classes of polyominoes. We give an algorithm for direct enumeration of permutominoes by size, or, equivalently, for the enumeration of grid orthogonal polygons. We show how the construction technique...

An orthogonal polygon of P is called "thin" if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum guard set for either a thin orthogonal polygon or only its vertices is NP-hard, indeed APX-hard, either for guards lying...

Given an arrangement A of n sensors and two points s and t in the plane, the barrier resilience of A with respect to s and t is the minimum number of sensors whose removal permits a path from s to t such that the path does not intersect the coverage region of any sensor in A. When the surveillance domain is the entire plane and sensor coverage...

We introduce a class of solids that can be constructed gluing stackable pieces, which has been proven to have advantages in architectural construction. We derive a necessary condition for a solid to belong to this class. This helps to specify a simple sufficient condition for the existence of a stackable tessellation of a given solid. Finally,...

An intriguing conjecture of Nandakumar and Ramana Rao is that for every convex body K ⊆ R2, and for any positive integer n, K can be expressed as the union of n convex sets with disjoint interiors and each having the same area and perimeter. The first difficult case- n = 3- was settled by Bárány, Blagojevi¢, and Szucs using powerful tools from...

In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1/4 n-1/2/2 n−2/2 n−3/2. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by x-monotone curves. In fact, our proof shows that the conjecture remains true...

A web-based system that determines point/curve and curve/curve bisectors in a dynamic geometry system in a completely automatic way is presented. The system consists of an interactive drawing canvas where the bisector is displayed together with the initial point/curve elements. Algebraic methods are used to provide the equation of an algebraic...

Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(γ) the length (the number of edges or the sum of the edge weights) of a cycle γ in G. The stretch of a graph embedded on a surface is the minimum of len(α)· len(β) over all pairs of cycles α and β that cross exactly once. We provide an algorithm...

A graph is crossing-critical if its crossing number decreases when we remove any of its edges. Recently it was proved that if a non-planar graph G is obtained by adding an edge to a cubic polyhedral (planar 3-connected) graph, then G can be made crossingcritical by a suitable multiplication of its edges. Here we show: (i) a new family of graphs...

In this paper we propose a new GPU method able to compute the 2D constrained Delaunay triangulation of a planar straight line graph consisting of points and segments. The method is based on an incremental insertion, taking special care to avoid conflicts during concurrent insertion of points into the triangulation and concurrent edge flips.

In 1979 Conway, Croft, Erd\H{o}s and Guy proved that every set SS of nn points in general position in the plane determines at least n3/18−O(n2) obtuse angles and also presented a special set of nn points to show the upper bound 2n3/27−O(n2) on the minimum number of obtuse angles among all sets SS. We prove that every set SS of nn points in...

In this paper we propose and solve common influence region queries. We present GPU parallel algorithms, designed under CUDA architecture, for approximately solving the studied queries. We also provide and discuss experimental results showing the efficiency of our approach.

Given a set P of points in Rd, a convex hole (alternatively, empty convex polytope) of P is a convex polytope with vertices in P, containing no points of P in its interior. Let R be a bounded convex region in Rd. We show that if P is a set of n random points chosen independently and uniformly over R, then the expected number of vertices of the...

The Minimum Weight Pseudo-Triangulation (MWPT) problem is suspected to be NP-hard. We show here how Simulated Annealing (SA) can be applied for obtaining approximate solutions to the optimal ones. To do that, we applied two SA algorithms, the basic version and our extended hybrid version of SA. Through the experimental evaluation and...

This paper focuses on a variation of the Art Gallery problem that considers open edge guards. The "open" prefix means the endpoints of an edge where a guard is are not taken into account for visibility purposes. This paper studies the number of open edge guards that are sufficient and sometimes necessary to guard some classes of simple polygons.

The invisibility graph I(X) of a set X ⊆ Rd is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X . We consider the following three parameters of a set X : the clique number ω(I(X)),...