A Geometric Theorem for Approximate Disk Covering Algorithms

Franceschetti, M. and Cook, M. and Bruck, J. (2001) A Geometric Theorem for Approximate Disk Covering Algorithms. Technical Report. California Institute of Technology. [CaltechPARADISE:2001.ETR035]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	PDF (Adobe PDF (1.9MB)) - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

We present a basic theorem in combinatorial geometry that leads to a family of approximation algorithms for the the geometric disk covering problem. These algorithms exhibit constant approximation factors, with a wide range of their choices. This flexibility allows to achieve a running time that compares favourably with those of existing procedures..

EPrint Type:	Monograph (Technical Report)
Additional Information:	[Alternate URL: http://www.paradise.caltech.edu/papers/etr035.ps]
Subjects:	All Records
ID Code:	14
Deposited By:	Jehoshua Bruck
Deposited On:	03 September 2002
Record Number:	CaltechPARADISE:2001.ETR035
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2001.ETR035
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record