Mutual witness proximity graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

    Research output: Contribution to journalArticlepeer-review


    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 languageEnglish (US)
    Pages (from-to)519-523
    Number of pages5
    JournalInformation Processing Letters
    Issue number10
    StatePublished - Oct 2014


    • 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


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

    Cite this