TY - JOUR
T1 - Mutual witness proximity graphs
AU - Aronov, Boris
AU - Dulieu, Muriel
AU - Hurtado, Ferran
N1 - Funding Information:
Boris Aronov and Muriel Dulieu were partially supported by grant No. 2006/194 from the United States – Israel Binational Science Foundation and by NSF Grants CCF-08-30691 , CCF-11-17336 , and CCF-12-18791 . Boris Aronov was also supported by NSA MSP Grant H98230- 10-1-0210 . Ferran Hurtado is partially supported by projects MEC MTM2006-01267 , MICINN MTM2009-07242 , MINECO MTM2012-30951 , Generalitat de Catalunya DGR 2009SGR1040 , and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: MICINN Project EUI-EURC-2011-4306 , for Spain.
Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014/10
Y1 - 2014/10
N2 - 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 worst case. We also show that if two mutual witness Delaunay graphs are complete, then the sets A and B are circularly separable; if two mutual witness Gabriel graphs are complete, then the sets A and B are linearly separable; but two mutual witness rectangle graphs might be complete, with A and B not linearly separable.
AB - 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 worst case. We also show that if two mutual witness Delaunay graphs are complete, then the sets A and B are circularly separable; if two mutual witness Gabriel graphs are complete, then the sets A and B are linearly separable; but two mutual witness rectangle graphs might be complete, with A and B not linearly separable.
KW - Computational geometry
KW - Delaunay graphs
KW - Gabriel graphs
KW - Proximity graphs
KW - Rectangle of influence graphs
KW - Witness graphs
UR - http://www.scopus.com/inward/record.url?scp=84899854890&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84899854890&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2014.04.001
DO - 10.1016/j.ipl.2014.04.001
M3 - Article
AN - SCOPUS:84899854890
VL - 114
SP - 519
EP - 523
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
IS - 10
ER -