# Dissertation/Thesis Abstract

Witness proximity graphs and other geometric problems
by Dulieu, Muriel, Ph.D., Polytechnic Institute of New York University, 2012, 115; 3518747
Abstract (Summary)

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.

Indexing (document details)
 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