Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
On Structural and graph theoretic properties of higher order Delaunay graphs
Año:2007
Áreas de investigación
  • Arquitectura de computadores
Datos
Descripción
Given a set $P$ of $n$ points in the plane, the order-$k$ Delaunay graph is a graph with vertex set $P$ and an edge exists between two points $p, q \in P$ when there is a circle through $p$ and $q$ with at most $k$ other points of $P$ in its interior. We provide upper and lower bounds on the number of edges in an order-$k$ Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-$k$ Delaunay graph is connected under the flip operation when $k\leq 1$ but not necessarily connected for other values of $k$. If $P$ is in convex position then the order-$k$ Delaunay graph is connected for all $k \geq 0$. We show that the order-$k$ Gabriel graph, a subgraph of the order-$k$ Delaunay graph, is Hamiltonian for $k\geq 15$. Finally, the order-$k$ Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks.
Internacional
Si
JCR del ISI
Si
Título de la revista
INT J COMPUT GEOM AP
ISSN
0218-1950
Factor de impacto JCR
0,298
Información de impacto
Volumen
--
DOI
Número de revista
0
Desde la página
--
Hasta la página
--
Mes
SIN MES
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: A. RAMOS (U. ALCALÁ HENARES)
  • Autor: M. ABELLANAS (UPM)
  • Autor: C.M. NICOLÁS
  • Autor: Jesus Garcia Lopez de Lacalle (UPM)
  • Autor: B. PROSENJIT
  • Autor: F. HURTADO (UPC)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Matemática Aplicada (E.U. Informática)
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)