Witness (Delaunay) graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

    Research output: Contribution to journalArticlepeer-review


    Proximity graphs are used in several areas in which a neighborliness relationship for input data sets is a useful tool in their analysis, and have also received substantial attention from the graph drawing community, as they are a natural way of implicitly representing graphs. However, as a tool for graph representation, proximity graphs have some limitations that may be overcome with suitable generalizations. We introduce a generalization, witness graphs, that encompasses both the goal of more power and flexibility for graph drawing issues and a wider spectrum for neighborhood analysis. We study in detail two concrete examples, both related to Delaunay graphs, and consider as well some problems on stabbing geometric objects and point set discrimination, that can be naturally described in terms of witness graphs.

    Original languageEnglish (US)
    Pages (from-to)329-344
    Number of pages16
    JournalComputational Geometry: Theory and Applications
    Issue number6-7
    StatePublished - Aug 2011


    • Delaunay graph
    • Graph drawing
    • Proximity graphs
    • Witness graphs

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'Witness (Delaunay) graphs'. Together they form a unique fingerprint.

    Cite this