Mutual witness proximity graphs

Boris Aronov; Muriel Dulieu; Ferran Hurtado

doi:10.1016/j.ipl.2014.04.001

Mutual witness proximity graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	519-523
Number of pages	5
Journal	Information Processing Letters
Volume	114
Issue number	10
DOIs	https://doi.org/10.1016/j.ipl.2014.04.001
State	Published - Oct 2014

Keywords

Computational geometry
Delaunay graphs
Gabriel graphs
Proximity graphs
Rectangle of influence graphs
Witness graphs

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2014.04.001

Fingerprint Dive into the research topics of 'Mutual witness proximity graphs'. Together they form a unique fingerprint.

Cite this

@article{b9cc2b38c7b046c195547c1080b9f822,

title = "Mutual witness proximity graphs",

abstract = "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.",

keywords = "Computational geometry, Delaunay graphs, Gabriel graphs, Proximity graphs, Rectangle of influence graphs, Witness graphs",

author = "Boris Aronov and Muriel Dulieu and Ferran Hurtado",

year = "2014",

month = oct,

doi = "10.1016/j.ipl.2014.04.001",

language = "English (US)",

volume = "114",

pages = "519--523",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

T1 - Mutual witness proximity graphs

AU - Aronov, Boris

AU - Dulieu, Muriel

AU - Hurtado, Ferran

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 -