|
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 ip operation when k <= 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 >= 0. We show that the order-k Gabriel graph, a subgraph of the order-k Delaunay graph, is Hamiltonian for k >= 15. Finally, the order-k Delaunay graph can be used to eciently solve a coloring problem with applications to frequency assignments in cellular networks. | |
|
Internacional
|
Si |
|
JCR del ISI
|
Si |
|
Título de la revista
|
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY AND APPLICATIONS |
|
ISSN
|
0218-1959 |
|
Factor de impacto JCR
|
0,436 |
|
Información de impacto
|
|
|
Volumen
|
19 |
|
DOI
|
10.1142/S0218195909003143 |
|
Número de revista
|
6 |
|
Desde la página
|
595 |
|
Hasta la página
|
615 |
|
Mes
|
DICIEMBRE |
|
Ranking
|
|