Pasar al contenido principal

GRAFOS GEOMETRICOS Y ABSTRACTOS: TEORIA Y APLICACIONES

PID2023-150725NB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2023
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On the number of quadrilaterals in higher order Voronoi diagrams

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Coloraciones por entornos en jaulas de Moore

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Araujo Pardo, Gabriela
A k-coloring of a graph G is a k-partition = S1 Sk of V(G) into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices uv belonging to the same color Si, the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number, denoted by NL(G), is the minimum cardinality of a neighbor-locating coloring of G. In this paper we study the neighbor-locating coloring of graphs that are Moore cages.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Tuttle, Tyler
Let ¿(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x,y ¿ S, where every geodesic disk containing x and y contains ¿(n) points of S. We establish upper and lower bounds for ¿(n), and show that n 5 +1 = ¿(n) = n 4 +1. We also show that there always exist two points x,y ¿ S such that every geodesic disk with x and y on its boundary contains at least 16 665 (n - 2) ˜ n-2 41.6 points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of n 3 +1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of n-2 two-colored version of the problem., G. E., D. O. and R. S. are partially supported by grants PID2019-104129GB-I00 and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. P. B. and T. T. are supported in part by NSERC., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Containment results on points and spheres

  • Heras Parrilla, Andrea de las
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Orden Martin, David
Let S be a set of n points in general position in R d . We show several containment results for points from S in spheres determined by d + 1 points of S. Among them, we prove a Delaunay-type criterion for point sets in R 3 . Also, we show bounds on the expected number of points from S contained in a sphere determined by four points chosen uniformly at random from S ¿ R 3 . A tight upper bound construction is provided, obtained by inversion of points on the moment curve. We also show a lower bound and prove that it is best possible for n = 7. In order to do so, we solve the recurrence relation T(n) = l n n-5 T(n - 1)m with base case T(7) = 29. This is of independent interest, since most recurrence relations of this type seem not to have a solution in closed form., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Shortest descending path is not solvable within ACMQ

  • Franco Sánchez, Victor|||0009-0007-4163-2476
  • Herrero Bravo, Alex
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
In this paper, we consider the Shortest Descending Path (SDP) Problem. The SDP Problem is the problem of computing a shortest path between two given points on a polyhedral terrain, with the additional constraint that the path may never increase in z coordinate. No polynomial algorithm is known to compute an SDP. In this paper, we present a construction demonstrating that an SDP is not computable within the ACMQ model, even in a terrain consisting of only three triangles. This result provides evidence of the diff iculty of solving the problem exactly.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Coloraciones por entornos en jaulas de Moore

  • Hernando Martín, María del Carmen
  • Araujo Pardo, Gabriela
A k-coloring of a graph G is a k-partition = S1 Sk of V(G) into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices uv belonging to the same color Si, the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number, denoted by NL(G), is the minimum cardinality of a neighbor-locating coloring of G. In this paper we study the neighbor-locating coloring of graphs that are Moore cages., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Shortest descending path is not solvable within ACMQ

  • Franco Sánchez, Victor
  • Herrero Bravo, Alex
  • Silveira, Rodrigo Ignacio
In this paper, we consider the Shortest Descending Path (SDP) Problem. The SDP Problem is the problem of computing a shortest path between two given points on a polyhedral terrain, with the additional constraint that the path may never increase in z coordinate. No polynomial algorithm is known to compute an SDP. In this paper, we present a construction demonstrating that an SDP is not computable within the ACMQ model, even in a terrain consisting of only three triangles. This result provides evidence of the diff iculty of solving the problem exactly., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Containment results on points and spheres

  • Heras Parrilla, Andrea de las
  • Flores Peñaloza, David
  • Huemer, Clemens
  • Orden Martin, David
Let S be a set of n points in general position in R d . We show several containment results for points from S in spheres determined by d + 1 points of S. Among them, we prove a Delaunay-type criterion for point sets in R 3 . Also, we show bounds on the expected number of points from S contained in a sphere determined by four points chosen uniformly at random from S ¿ R 3 . A tight upper bound construction is provided, obtained by inversion of points on the moment curve. We also show a lower bound and prove that it is best possible for n = 7. In order to do so, we solve the recurrence relation T(n) = l n n-5 T(n - 1)m with base case T(7) = 29. This is of independent interest, since most recurrence relations of this type seem not to have a solution in closed form., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
  • Tuttle, Tyler
Let ¿(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x,y ¿ S, where every geodesic disk containing x and y contains ¿(n) points of S. We establish upper and lower bounds for ¿(n), and show that n 5 +1 = ¿(n) = n 4 +1. We also show that there always exist two points x,y ¿ S such that every geodesic disk with x and y on its boundary contains at least 16 665 (n - 2) ˜ n-2 41.6 points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of n 3 +1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of n-2 two-colored version of the problem., G. E., D. O. and R. S. are partially supported by grants PID2019-104129GB-I00 and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. P. B. and T. T. are supported in part by NSERC., Peer Reviewed, Postprint (published version)
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo|||0000-0002-0751-7729
  • Orden Martín, David|||0000-0001-5403-8467
  • Silveira, Rodrigo I.
  • Tuttle, Tyler
19th International Symposium on Algorithms and Data Structures (WADS 2025)., Let Π(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x, y ∈ S, where every geodesic disk containing x and y contains Π(n) points of S. We establish upper and lower bounds for Π(n), and show that ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +1. We also show that there always exist two points x, y ∈ S such that every geodesic disk with x and y on its boundary contains at least 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem., Agencia Estatal de Investigación