Title: 

Finding an Approximate Minimum-Link Visibility Path Inside a 
Simple Polygon

Muhammad H. Alsuwaiyel
Department of Information and Computer Science
King Fahd University of Petroleum \& Minerals
Dhahran 31261, Saudi Arabia
e-mail:facp079@saupm00.bitnet

and 

D.T. Lee*
Department of Electrical and Computer Engineering 
Northwestern University 
Evanston, IL 60208
e-mail: dtlee@ece.nwu.edu

* Supported in part by the National Science Foundation
  under the Grant CCR-9309743, and by the Office of Naval Research
  under the Grant No. N00014-93-1-0272

Abstract:

We show that an approximate minimum link visibility path as well as 
a tour in a simple polygon of n sides can be computed in O(n^2) time, 
and that the link-length produced by the approximation algorithm 
is no more than 4 times that of the optimal algorithm.
The performance ratio can be improved to 3.5 with an algorithm that
runs in O(n^3) time.

Keywords: Computational geometry, approximation algorithm, 
	  simple polygon, visibility path, minimum link path.

Information Processing Letters, 55 (1995) 75-79.