Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Mutual witness proximity graphs

Autor
Aronov, B.; Dulieu, M.; Hurtado, F.
Tipus d'activitat
Article en revista
Revista
Information processing letters
Data de publicació
2014-10-01
Volum
114
Número
10
Pàgina inicial
519
Pàgina final
523
DOI
https://doi.org/10.1016/j.ipl.2014.04.001 Obrir en finestra nova
Projecte finançador
Geometría Discreta: Problemas de Combinatoria y Computación
Morfología geométrica computacional.
Métodos algorítmicos y estructuras combinatorias en geometría computacional
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
URL
http://www.sciencedirect.com/science/article/pii/S002001901400060X Obrir en finestra nova
Resum
This paper describes one variation on witness proximity graphs called mutual witness proximity graphs. Two witness proximity graphs are said to be mutual when, given two sets of points A and B, A is the vertex set of the first graph and the witness set of the second one, while B is the witness set of the first graph and the vertex set of the second one. We show that in the union of two mutual witness Delaunay graphs, there are always at least n-22 edges, where n=|A|+|B|, which is tight in the wo...
Paraules clau
Computational geometry, Delaunay graphs, Gabriel graphs, Proximity graphs, Rectangle of influence graphs, Witness graphs
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Aronov, Boris  (autor)
  • Dulieu, Muriel  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)