| Description |
Point sets on the plane are a fundamental class of objects studied in discrete and computational geometry, with many applications in real life problems. In this seminar, we discuss the following three problems on planar point sets.
A triangulation of a planar point set P is a plane graph in which every face (except the outer face) is a triangle. A planar point set P is k-connectible if there exists a k-connected plane graph G with vertex set P and all edges as line segments. We characterize all 4-connectible point sets and give an O(n^3) time algorithm to compute such a triangulation. Thus, we solve a longstanding open problem in computational geometry and geometric graph theory.
Two points p and q of a point set P are mutually visible if the line segment pq does not contain or pass through any other point of P. The point visibility graph G of P (referred to as PVG) is defined by associating a vertex with each point of P such that (v,w) is an undirected edge of G iff their corresponding points p and q are visible. Identifying a set of properties satisfied by all PVGs is called the PVG characterization problem. We give three necessary conditions for characterizing PVGs, and discuss properties of PVGs. We completely characterize planar PVGs.
The problem of determining if there is a set of points P whose PVG is the given graph G, is called the visibility graph recognition problem. We show that the PVG recognition problem is NP-hard using collinearity restrictions for points.
|