Witness (Delaunay) graphs
From MaRDI portal
Publication:551502
DOI10.1016/J.COMGEO.2011.01.001zbMATH Open1232.05190arXiv1008.1053OpenAlexW1993789161MaRDI QIDQ551502FDOQ551502
Muriel Dulieu, Boris Aronov, Ferran Hurtado
Publication date: 20 July 2011
Published in: Computational Geometry (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1008.1053
Recommendations
Cites Work
- Sphere-of-attraction graphs
- Graph Classes: A Survey
- Title not available (Why is that?)
- Voronoi diagrams and arrangements
- A short proof of Chvatal's Watchman Theorem
- Modular decomposition and transitive orientation
- Title not available (Why is that?)
- A linear algorithm for determining the separation of convex polyhedra
- On empty triangles determined by points in the plane
- Graph-theoretical conditions for inscribability and Delaunay realizability
- Voronoi drawings of trees
- Covering the convex quadrilaterals of point sets
- Title not available (Why is that?)
- Partially Ordered Sets
- Simpler proof of a realizability theorem on Delaunay triangulations
- An optimal algorithm for realizing a Delaunay triangulation
- Title not available (Why is that?)
- Realizability of Delaunay triangulations
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Toughness and Delaunay triangulations
- Competitive facility location: the Voronoi game
- Trees that are sphere-of-influence graphs
- Witness Rectangle Graphs
- The strength of weak proximity
- Title not available (Why is that?)
- MAXIMIZING A VORONOI REGION: THE CONVEX CASE
- Transitions in geometric minimum spanning trees
- Characterizing proximity trees
- The rectangle of influence drawability problem
- Computing the intersection-depth to polyhedra
- Title not available (Why is that?)
- Fast detection of polyhedral intersection
- The relative neighborhood graph for mixed feature variables
- Motion planning for a convex polygon in a polygonal environment
- Efficient algorithms for bichromatic separability
- A general approach to dominance in the plane
- Discrete and Computational Geometry
Cited In (13)
- Mutual witness proximity drawings of isomorphic trees
- PROXIMITY DRAWINGS OF HIGH-DEGREE TREES
- Mutual witness proximity graphs
- Approximate Proximity Drawings
- Carathéodory's theorem in depth
- Hitting and Piercing Rectangles Induced by a Point Set
- Witness rectangle graphs
- Mutual witness Gabriel drawings of complete bipartite graphs
- Approximate proximity drawings
- Witnessed \(k\)-distance
- Witness Gabriel graphs
- Mutual witness Gabriel drawings of complete bipartite graphs
- The Mathematics of Ferran Hurtado: A Brief Survey
Uses Software
This page was built for publication: Witness (Delaunay) graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551502)
