Output sensitive algorithms for covering many points

Hossein Ghasemalizadeh 1 Mohammadreza Razzazi 1
1 SSRD - Software system research and development Laboratory [Tehran]
CEIT - Computer Engineering and Information technology department (Tehran)
Abstract : In this paper we devise some output sensitive algorithms for a problem where a set of points and a positive integer, m, are given and the goal is to cover a maximal number of these points with m disks. We introduce a parameter, ρ, as the maximum number of points that one disk can cover and we analyse the algorithms based on this parameter. At first, we solve the problem for m=1 in O(nρ) time, which improves the previous O(n2) time algorithm for this problem. Then we solve the problem for m=2 in O(nρ + 3 log ρ) time, which improves the previous O(n3 log n) algorithm for this problem. Our algorithms outperform the previous algorithms because ρ is much smaller than n in many cases. Finally, we extend the algorithm for any value of m and solve the problem in O(mnρ + (mρ)2m - 1 log mρ) time. The previous algorithm for this problem runs in O(n2m - 1 log n) time and our algorithm usually runs faster than the previous algorithm because mρ is smaller than n in many cases. We obtain output sensitive algorithms by confining the areas that we should search for the result. The techniques used in this paper may be applicable in other covering problems to obtain faster algorithms.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.309--316
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196845
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:05
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:00:38

Fichier

dmtcs-17-1-20.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196845, version 1

Collections

Citation

Hossein Ghasemalizadeh, Mohammadreza Razzazi. Output sensitive algorithms for covering many points. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.309--316. 〈hal-01196845〉

Partager

Métriques

Consultations de la notice

65

Téléchargements de fichiers

99