nach oben

Theory of Computing Systems

Erschienen in:

11.06.2018

The Most Points Connected-Covering Problem with Two Disks

verfasst von: Sanaz Soltani, Mohammadreza Razzazi, Hossein Ghasemalizadeh

Erschienen in: Theory of Computing Systems | Ausgabe 8/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Online Bin Packing with Advice of Small Size

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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)

Titel: The Most Points Connected-Covering Problem with Two Disks
verfasst von: Sanaz Soltani
Mohammadreza Razzazi
Hossein Ghasemalizadeh
Publikationsdatum: 11.06.2018
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 8/2018
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9870-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 8/2018

Parameterised Algorithms for Deletion to Classes of DAGs

Online Bin Packing with Advice of Small Size

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

Set Cover Problems with Small Neighborhood Covers

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

Finger Search in Grammar-Compressed Strings