Pasar al contenido principal

Resultados relacionados

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

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Blocking the k-Holes of Point Sets in the Plane

  • Cano, Javier
  • García, Alfredo
  • Hurtado, Ferran
  • Sakai, Toshinori
  • Tejel, Javier
  • Urrutia, Jorge
Let P be a set of n points in the plane in general position. A subset H of P consisting of k elements that are the vertices of a convex polygon is called a k-hole of P, if there is no element of P in the interior of its convex hull. A set B of points in the plane blocks the k-holes of P if any k-hole of P contains at least one element of B in the interior of its convex hull. In this paper we establish upper and lower bounds on the sizes of k-hole blocking sets, with emphasis in the case k=5.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Colored ray configurations

  • Fabila-Monroy, R.
  • García, A.
  • Hurtado, F.
  • Jaume, R.
  • Pérez-Lantero, P.
  • Saumell, M.
  • Silveira, R.I.
  • Tejel, J.
  • Urrutia, J.
We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be T(n2) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Geometric biplane graphs II: graph augmentation

  • Garcia Olaverri, Alfredo Martin
  • Hurtado Díaz, Fernando Alfredo
  • Korman Cozzetti, Matías
  • Matos, Inés P.
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio
  • Tejel Altarriba, Francisco Javier
  • Tóth, Csaba D.
We study biplane graphs drawn on a finite point set in the plane in general position. This is the family of geometric graphs whose vertex set is and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

New results on stabbing segments with a polygon

  • Díaz Bañez, José Miguel
  • Korman Cozzetti, Matías
  • Pérez Lantero, Pablo
  • Pilz, Alexander
  • Seara Ojea, Carlos
  • Silveira, Rodrigo Ignacio
We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s is stabbed by a simple polygon P if at least one endpoint of s is contained in P, and a segment set S is stabbed by P if P stabs every element of S. Given a segment set S, we study the problem of finding a simple polygon P stabbing S in a way that some measure of P (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by Loftier and van Kreveld [Algorithmica 56(2), 236-269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard. (C) 2014 Elsevier B.V. All rights reserved., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Geometric biplane graphs I: maximal graphs

  • Garcia Olaverri, Alfredo Martin
  • Hurtado Díaz, Fernando Alfredo
  • Korman Cozzetti, Matías
  • Matos, Inés P.
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio
  • Tejel Altarriba, Francisco Javier
  • Tóth, Csaba D.
We study biplane graphs drawn on a finite planar point set in general position. This is the family of geometric graphs whose vertex set is and can be decomposed into two plane graphs. We show that two maximal biplane graphs-in the sense that no edge can be added while staying biplane-may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over -element point sets., Peer Reviewed, Postprint (author's final draft)