Title :
Best regular enclosures for triangles
Author_Institution :
Dept. of Comput. Sci., New Orleans Univ., LA
Abstract :
An interesting variant of polygon approximation problems is described: for a given convex polygon P, which of the smallest k-gonal enclosures for P, k⩾3, has minimum area? A proof of the finite nature of the value of k which answers this problem (the Kosaraju number of the polygon), as well as several of its other versions, is outlined. The provable upper bounds on Kosaraju numbers turn out to be exponential in the number of edges of the enclosed polygon, making the search for exact values potentially intractable. It is shown that when the polygons involved are the simplest possible-triangles-the Kosaraju number is always equal to 3
Keywords :
computational geometry; Kosaraju number; convex polygon; polygon approximation problems; upper bounds; Algorithm design and analysis; Boolean functions; Computational geometry; Computer science; Data structures; History; Motion analysis; Upper bound;
Conference_Titel :
Southeastcon '88., IEEE Conference Proceedings
Conference_Location :
Knoxville, TN
DOI :
10.1109/SECON.1988.194879