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.
|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|
|Subjects:||Applied Mathematics, Computer science|
|Keywords:||Computational geometry, Geometric problems, Graph theory, Proximity graphs|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be