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
|