ON CLUSTERING TO MINIMIZE THE SUM OF RADII

Matt Gibson; Gaurav Kanade; Erik Krohn; Imran A. Pirwani; Kasturi Varadarajan

doi:10.1137/100798144

Back

ON CLUSTERING TO MINIMIZE THE SUM OF RADII

Journal article

Peer reviewed

ON CLUSTERING TO MINIMIZE THE SUM OF RADII

Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani and Kasturi Varadarajan

SIAM journal on computing, Vol.41(1), pp.47-60

01/01/2012

DOI: 10.1137/100798144

View Online

Abstract

Let P be a set of n points in the plane. Consider the problem of finding k disks, each centered at a point in P, whose union covers P with the objective of minimizing the sum of the radii of the disks. We present an exact algorithm for this well-studied problem with polynomial running time, under the assumption that two candidate solutions can be compared efficiently. The algorithm generalizes in a straightforward manner to any fixed dimension and to some other related problems.

Computer Science

Computer Science, Theory & Methods

Mathematics

Mathematics, Applied

Physical Sciences

Science & Technology

Technology

Details

Title: Subtitle: ON CLUSTERING TO MINIMIZE THE SUM OF RADII
Creators: Matt Gibson - matthew-gibson@uiowa.edu
Gaurav Kanade - gaurav.kanade@gmail.com and kasturi-varadarajan@uiowa.edu
Erik Krohn - Oshkosh
Imran A. Pirwani - imran.pirwani@gmail.com
Kasturi Varadarajan - University of Iowa
Resource Type: Journal article
Publication Details: SIAM journal on computing, Vol.41(1), pp.47-60
Publisher: Siam Publications
DOI: 10.1137/100798144
ISSN: 0097-5397
eISSN: 1095-7111
Number of pages: 14
Grant note: Alberta Ingenuity CCR 0237431 / NSF; National Science Foundation (NSF)
Language: English
Date published: 01/01/2012
Academic Unit: Computer Science
Record Identifier: 9984259437502771

Metrics

5 Record Views

6 Times Cited - Web of Science

See more details