Top

Theory of Computing Systems

Published in:

11-06-2018

The Most Points Connected-Covering Problem with Two Disks

Authors: Sanaz Soltani, Mohammadreza Razzazi, Hossein Ghasemalizadeh

Published in: Theory of Computing Systems | Issue 8/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Let P be a set of points in the plane. The goal is to place two unit disks in the plane such that the number of points from P covered by the disks is maximized. In addition, the distance between the centers of the two disks should not exceed a specified constant R_c ≥ 0. We propose two algorithms to solve this problem. The first algorithm is a simple exhaustive algorithm which runs in O(n⁴) time. We then improve this algorithm by a constructing connectivity region and building a segment tree to compute two optimal disks. The resulting algorithm has \(O(n^{3} \log n)\) time complexity.

previous article Online Bin Packing with Advice of Small Size

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

For the cases that the graph is not connected, it can be connected by adding some extra edges between connected sub-graphs.

Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett. 12(3), 133–137 (1981)MathSciNetCrossRefMATH

Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM (JACM) 32(1), 130–136 (1985)MathSciNetCrossRefMATH

Gonzalez, T.F.: Covering a set of points in multidimensional space. Inform. Process. Lett. 40(4), 181–188 (1991)MathSciNetCrossRefMATH

Fu, B.: Theory and application of width bounded geometric separator. In: STACS. Springer, pp. 277–288 (2006)

Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithm. 53(1), 55–84 (2004)MathSciNetCrossRefMATH

de Berg, M., Cabello, S., Har-Peled, S.: Covering many or few points with unit disks. Theory Comput. Syst. 45(3), 446–469 (2009)MathSciNetCrossRefMATH

Cabello, S., Díaz-Báñez, J.M., Pérez-Lantero, P.: Covering a bichromatic point set with two disjoint monochromatic disks. Comput. Geom. 46(3), 203–212 (2013)MathSciNetCrossRefMATH

Cabello, S., Díaz-Báñez, J.M., Seara, C., Sellares, J.A., Urrutia, J., Ventura, I.: Covering point sets with two disjoint disks or squares. Comput. Geom. 40(3), 195–206 (2008)MathSciNetCrossRefMATH

Aronov, B., Dulieu, M.: How to cover a point set with a v-shape of minimum width. Comput. Geom. 46(3), 298–309 (2013)MathSciNetCrossRefMATH

10.

Kar, K., Banerjee, S., et al.: Node Placement for Connected Coverage in Sensor Networks. In: Wiopt’03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (2003)

11.

Ghosh, A., Das, S.K.: Coverage and connectivity issues in wireless sensor networks, Mobile, Wireless, and Sensor Networks: Technology, Applications, and Future Directions, pp. 221–256 (2006)

12.

Huang, P. -H., Tsai, Y.T., Tang, C.Y.: A fast algorithm for the alpha-connected two-center decision problem. Inform. Process. Lett. 85(4), 205–210 (2003)MathSciNetCrossRefMATH

13.

Drezner, Z.: Note—on a modified one-center model. Manag. Sci. 27(7), 848–851 (1981)CrossRefMATH

14.

Boissonnat, J.-D., Teillaud, M.: Effective computational geometry for curves and surfaces. Springer, Berlin (2006)CrossRefMATH

15.

Chazelle, B.M., Lee, D.-T.: On a circle placement problem. Computing 36 (1-2), 1–16 (1986)MathSciNetCrossRefMATH

16.

Ghasemalizadeh, H., Razzazi, M.: Output sensitive algorithm for covering many points. Discret. Math. Theor. Comput. Sci. 17(1), 309–316 (2015)MathSciNetMATH

17.

Ghasemalizadeh, H., Razzazi, M.: An improved approximation algorithm for the most points covering problem. Theory Comput. Syst. 50(3), 545–558 (2012)MathSciNetCrossRefMATH

18.

De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational geometry. Springer, Berlin (2000)

Title: The Most Points Connected-Covering Problem with Two Disks
Authors: Sanaz Soltani
Mohammadreza Razzazi
Hossein Ghasemalizadeh
Publication date: 11-06-2018
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 8/2018
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9870-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 8/2018

Primitivity, Uniform Minimality, and State Complexity of Boolean Operations

Parameterised Algorithms for Deletion to Classes of DAGs

Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels

Reasoning About XML Constraints Based on XML-to-Relational Mappings

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks

Premium Partner