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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3887061 (Why is no real title available?)
- scientific article; zbMATH DE number 177829 (Why is no real title available?)
- scientific article; zbMATH DE number 1182913 (Why is no real title available?)
- scientific article; zbMATH DE number 2079335 (Why is no real title available?)
- scientific article; zbMATH DE number 1424293 (Why is no real title available?)
- A general approach to dominance in the plane
- A linear algorithm for determining the separation of convex polyhedra
- A short proof of Chvatal's Watchman Theorem
- An optimal algorithm for realizing a Delaunay triangulation
- Characterizing proximity trees
- Competitive facility location: the Voronoi game
- Computational geometry. Algorithms and applications.
- Computing the intersection-depth to polyhedra
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Covering the convex quadrilaterals of point sets
- Efficient algorithms for bichromatic separability
- Fast detection of polyhedral intersection
- Graph Classes: A Survey
- Graph-theoretical conditions for inscribability and Delaunay realizability
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- MAXIMIZING A VORONOI REGION: THE CONVEX CASE
- Modular decomposition and transitive orientation
- Motion planning for a convex polygon in a polygonal environment
- On empty triangles determined by points in the plane
- Open problems in geometric methods for instance-based learning
- Partially Ordered Sets
- Realizability of Delaunay triangulations
- Simpler proof of a realizability theorem on Delaunay triangulations
- Sphere-of-attraction graphs
- The rectangle of influence drawability problem
- The relative neighborhood graph for mixed feature variables
- The strength of weak proximity
- Toughness and Delaunay triangulations
- Transitions in geometric minimum spanning trees
- Trees that are sphere-of-influence graphs
- Voronoi diagrams and arrangements
- Voronoi drawings of trees
- Witness rectangle graphs
Cited in
(15)- Approximate proximity drawings
- Proximity structures for geometric graphs
- Witness rectangle graphs
- Proximity drawings of high-degree trees
- Approximate proximity drawings
- Witness rectangle graphs
- Witness Gabriel graphs
- Witnessed \(k\)-distance
- The Mathematics of Ferran Hurtado: A Brief Survey
- Proximity structures for geometric graphs.
- Mutual witness proximity graphs
- Hitting and Piercing Rectangles Induced by a Point Set
- Mutual witness proximity drawings of isomorphic trees
- Mutual witness Gabriel drawings of complete bipartite graphs
- Mutual witness Gabriel drawings of complete bipartite graphs
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)
