Congreso de Geometría Computacional (15º. 2013. Sevilla)

URI permanente para esta colecciónhttps://hdl.handle.net/11441/59964

Examinar

Mostrando 1 - 20 de 35

Recent developments on the crossing number of the complete graph
(2013) Ramos Alonso, Pedro Antonio; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
Flips in combinatorial pointed pseudo-triangulations with face degree at most four
(2013) Aichholzer, Oswin; Hackl, Thomas; Orden Martín, David; Pilz, Alexander; Saumell Mendiola, María; Vogtenhuber, Birgit; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the flip graph of combinatorial 4-PPTs with triangular outer face is connected and has diameter O(n2).
Monotone crossing number of complete graphs
(2013) Balko, Martin; Fulek, Radoslav; Kynčl, Jan; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 for xmonotone drawings in which adjacent edges do not cross and we count only pairs of edges which cross odd number of times. We also discuss a combinatorial characterization of these drawings.
On 4-connected geometric graphs
(2013) García Olaverri, Alfredo; Huemer, Clemens; Tejel Altarriba, Francisco Javier; Valtr, Pavel; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
Given a set S of n points in the plane, in this paper we give a necessary and sometimes sufficient condition to build a 4-connected non-crossing geometric graph on S.
Phase transitions in the Ramsey-Turán theory
(2013) Balogh, József; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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, c√n log n )= n2/4 + o (n2) for c > 1, so one can say that K5 has a Ramsey-Turán-phase transition at c√n log n. We extend this result to several other Kp's and functions f(n), determining many more phase transitions. We shall formulate several open problems, in particular, whether variants of the Bollobás-Erdos graph, which is a geometric construction, exist to give good lower bounds on RT (n, Kp, f(n)) for various pairs of p and f(n). These problems are studied in depth by Balogh-HuSimonovits, where among others, the Szemerédi's Regularity Lemma and the Hypergraph Dependent Random Choice Lemma are used.
The alternating path problem revisited
(2013) Claverol Aguas, Mercè; Garijo Royo, Delia; Hurtado Díaz, Ferran; Lara Cuevas, María Dolores; Seara Ojea, Carlos; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 obtained on all instances. We also extend this kind of result to other configurations and provide remarks on similar problems.
Witness bar visibility
(2013) Cortés Parejo, María del Carmen; Hurtado Díaz, Ferran; Márquez Pérez, Alberto; Valenzuela Muñoz, Jesús; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge; Universidad de Sevilla. FQM164: Matemática Discreta: Teoría de Grafos y Geometría Computacional
Bar visibility graphs were introduced in the seventies as a model for some VLSI layout problems. They have been also studied since then by the graph drawing community, and recently several generalizations and restricted versions have been proposed. We introduce a generalization, witness-bar visibility graphs, and we prove that this class encompasses all the bar-visibility variations considered so far. In addition, we show that many classes of graphs are contained in this family, including in particular all planar graphs, interval graphs, circular arc graphs and permutation graphs.
On making a graph crossing-critical
(2013) Hernández Vélez, César Israel; Leaños Macías, Jesús; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 that can be transformed into crossing-critical graphs by a suitable multiplication of its edges, and (ii) a family of graphs that cannot be made crossing-critical by any multiplication of its edges.
On three parameters of invisibility graphs
(2013) Cibulka, Josef; Korbelář, Miroslav; Kynčl, Jan; Mészáros, Viola; Stolař, Rudolf; Valtr, Pavel; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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)), the chromatic number χ(I(X)) and the inimum number γ(X) of convex subsets of X that cover X. We settle a conjecture of Matousek and Valtr claiming that for every planar set X, γ(X) can be bounded in terms of χ(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has χ(I(X)) ≥ log log(n) but ω(I(X)) = 3. We also find sets X in R5 with χ(I(X)) = 2, but γ(X) arbitrarily large.
Improved enumeration of simple topological graphs
(2013) Kynčl, Jan; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 and H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author's previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph G with n vertices, m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize G is at most 2 O(n2log(m/n)), and at most 2O(mn1/2 log n) if m ≤ n 3/2. As a consequence we obtain a new upper bound 2 O(n3/2 log n) on the number of intersection graphs of n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with n vertices to 2n2 ·α(n) O(1), using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize G is at most 2 m2+O(mn) and at least 2 Ω(m2) for graphs with m > (6 + ε)n.
Stackable tessellations
(2013) Enrique Monzo, Lluís; Jaume Deyà, Rafel; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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, we show the compatibility of our method with some discretization techniques appearing in the literature.
Stabbing simplices of point sets with k-flats
(2013) Cano Vila, Javier; Hurtado Díaz, Ferran; Urrutia Galicia, Jorge; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 plane and in R3.
Note on the number of obtuse angles in point sets
(2013) Fabila Monroy, Ruy; Huemer, Clemens; Tramuns Figueras, Eulàlia; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 convex position determines at least 2n327−o(n3)2n327−o(n3) obtuse angles, hence matching the upper bound (up to sub-cubic terms) in this case. Also on the other side, for point sets with low rectilinear crossing number, the lower bound on the minimum number of obtuse angles is improved.
Empty convex polytopes in random point sets
(2013) Balogh, József; González Aguilar, Hernán; Salazar Anaya, Gelasio; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 largest hole of P is Θ(log n/(log log n)), regardless of the shape of R. This generalizes the analogous result proved for the case d = 2 by Balogh, González-Aguilar, and Salazar.
Simulating distributed algorithms for lattice agents
(2013) Aichholzer, Oswin; Hackl, Thomas; Sacristán Adinolfi, Vera; Vogtenhuber, Birgit; Wallner, Reinhardt; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
We present a practical Java tool for simulating synchronized distributed algorithms on sets of 2-and 3-dimensional square/cubic lattice-based agents. This AgentSystem assumes that each agent is capable to change position in the lattice and that neighboring agents can attach and detach from each other. In addition, it assumes that each module has some constant size memory and computation capability, and can send/receive constant size messages to/from its neighbors. The system allows the user to dene sets of agents and sets of rules and apply one to the other. The AgentSystem simulates the synchronized execution of the set of rules by all the modules, and can keep track of all actions made by the modules at each step, supporting consistency warnings and error checking. Our intention is to provide a useful tool for the researchers from geometric distributed algorithms.
A symbolic-numeric dynamic geometry environment for the computation of equidistant curves
(2013) Abánades Astudillo, Miguel Ángel; Botana Ferreiro, Francisco; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 variety containing the bisector. A numeric approach is followed to provide the graph of the semi-algebraic subset corresponding to the true bisector. It is based on the free dynamic geometry system GeoGebra and the open source computer algebra system Sage.
Simulated annealing applied to the MWPT problem
(2013) Gagliardi, Edilma Olinda; Leguizamón, Mario Guillermo; Hernández Peñalver, Gregorio; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 statistical study we assess the applicability and performance of the SA algorithms. The obtained results show the benefits of using the hybrid version of SA to achieve improved and higher quality solutions for the MWPT problem.
SensoGraph: Using proximity graphs for sensory analysis
(2013) Miguel, David N. de; Orden Martín, David; Fernández Fernández, Encarnación; Rodríguez Nogales, José Manuel; Vila Crespo, Josefina; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
Sensory evaluation of foods is as important as chemical, physical or microbiological examinations, being specially relevant in food industries. Classical methods can be long and costly, making them less suitable for certain industries like the wine industry. Some alternatives have arisen recently, including Napping®, where the tasters represent the sensory distances between products by positioning them on a tablecloth; the more similar they perceive the products, the closer they position them on the tablecloth. This method uses multiple factor analysis (MFA) to process the data collected. The present paper introduces the software SensoGraph, which makes use of proximity graphs to analyze those data. The application is described and experimental results are presented in order to compare the performances of SensoGraph and Napping®, using eight wines from the Toro region and two groups of twelve tasters with different expertise.
Drawing the double circle on a grid of minimum size
(2013) Bereg, Sergey; Fabila Monroy, Ruy; Flores Peñaloza, David; Lopez, Mario A.; Pérez Lantero, Pablo; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
In 1926, Jarník introduced the problem of drawing a convex n-gon with vertices having integer coordinates. He constructed such a drawing in the grid [1, c ·n 3/2]2 for some constant c > 0, and showed that this grid size is optimal up to a constant factor. We consider the analogous problem of drawing the double circle, and prove that it can be done within the same grid size. Moreover, we give an O(n log n)-time algorithm to construct such a point set.
On the nonexistence of k-reptile simplices in R3 and R4
(2013) Kynčl, Jan; Safernova, Zuzana; Universidad de Sevilla. Departamento de Matemática Aplicada II; Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge
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 other hand, the only k-reptile simplices that are known for d≥3, have k=m d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d=3, k-reptile tetrahedra can exist only for k=m 3. We also prove a weaker analogue of this result for d=4 by showing that four-dimensional k-reptile simplices can exist only for k=m 2.

Examinar

Envíos recientes