With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
We introduce a generalization of the proximity graphs, the witness proximity graphs. We study in detail many concrete examples, and consider as well some problems on stabbing geometric objects and point set discrimination, that can be naturally described in terms of witness (proximity) graphs.
The witness graph of a point set P of vertices in the plane, with respect to a point set W of witnesses, is the graph with vertex set P in which two points x,y in P are adjacent if and only if they define a region, the region of influence, that does (positive version) or does not (negative version) contain a witness w in W. In a positive witness graph, witnesses, which are said to be positive, are necessary to have an edge between a pair of points, and in a negative witness graph, witnesses, which are said to be negative, remove edges between pairs of points.
As examples of witness graphs, we introduce two generalizations of the Delaunay graph, the witness Delaunay graph and the square graph for which the regions of influence are respectively the Delaunay disks (disks with two vertices on their boundary), and squares with two vertices on their boundary. We introduce also generalizations of the Gabriel graph and the rectangular influence graph, the witness Gabriel graph and the witness rectangle graph, for which the regions of influence are respectively the Gabriel disks (disks with diameters defined by a pair of vertices), and axis-parallel rectangles with diagonals defined by a pair of vertices. Finally we introduce a generalization of the relative neighborhood graph, the witness relative neighborhood graph with negative witnesses. In this witness graph, the region of influence is a lens, which is the intersection of two disks with a pair of vertices as centers and radii equal to the distance between these two vertices. For all these witness proximity graphs, we present some construction algorithms, worst-case and/or output-sensitive, as well as partial or complete characterization of the graphs.
Subsequently, we introduce some variations on the witness graphs. In one variation we show the interrelation between two witness proximity graphs defined by two sets of points A and B such that in the first witness graph, A is the set of vertices and B is the set of witnesses, and in the second witness graph, B is the set of vertices and A is the set of witnesses. The three witness proximity graphs studied in this particular case are the witness Delaunay graph, the witness Gabriel graph, and the witness rectangle graph. In another variation, we study a special case of witness rectangle graph with positive and negative witnesses at the same time.
Finally, we conclude with some related results on the number of points required to stab all the Delaunay disks, squares, Gabriel disks, rectangles, or lenses defined by pairs of points in a set of n points.
Advisor: | Aronov, Boris |
Commitee: | Hurtado, Ferran, Pach, Janos, Steiger, William |
School: | Polytechnic Institute of New York University |
Department: | Computer Science and Engineering |
School Location: | United States -- New York |
Source: | DAI-B 73/12(E), Dissertation Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Applied Mathematics, Computer science |
Keywords: | Computational geometry, Geometric problems, Graph theory, Proximity graphs |
Publication Number: | 3518747 |
ISBN: | 978-1-267-50644-3 |