Record Details

Four-Connected Triangulations of Planar Point Sets

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Four-Connected Triangulations of Planar Point Sets
 
Creator DIWAN, AA
GHOSH, SK
ROY, B
 
Subject Triangulation
4-connected
Complex triangle
Convex hull
Matching
Good set
Annular region
Inward triangle
Forbidden triangle
 
Description In this paper, we consider the problem of determining in polynomial time whether a given planar point set of points in general position admits a 4-connected triangulation. We propose a necessary and sufficient condition for recognizing such point sets , and present an time algorithm for constructing a 4-connected triangulation of , if it exists. Thus, our algorithm solves a longstanding open problem in computational geometry and geometric graph theory. We also provide a simple time method for constructing a non-complex triangulation of , if it exists. This method provides a new insight into the structure of 4-connected triangulations of point sets.
 
Publisher SPRINGER
 
Date 2016-01-14T11:00:41Z
2016-01-14T11:00:41Z
2015
 
Type Article
 
Identifier DISCRETE & COMPUTATIONAL GEOMETRY, 53(4)713-746
0179-5376
1432-0444
http://dx.doi.org/10.1007/s00454-015-9694-x
http://dspace.library.iitb.ac.in/jspui/handle/100/17422
 
Language en