Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Optimizing Squares Covering a Set of Points

verfasst von : Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, Priya Ranjan Sinha Mahapatra, Zhao Song

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We investigate two kinds of optimization problems regarding points in the 2-dimensional plane that need to be enclosed by squares.
(1)
Given a set of \(n\) points, find a given number of squares that enclose all the points, minimizing the size of the largest square used.
 
(2)
Given a set of \(n\) points, enclose the maximum number of points, using a specified number of squares of a fixed size. We provide different techniques to solve the above problems in cases where squares are axis-parallel or of arbitrary orientation, disjoint or overlapping. All the algorithms we use run in time that is a low-order polynomial in \(n\).
 

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 "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

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
Vorheriges Kapitel Randomized Online Algorithms for Set Cover Leasing Problems
Nächstes Kapitel Algorithms for Fair Partitioning of Convex Polygons
Fußnoten
1
This polygon may be the convex hull of the points in \(\mathcal P\) computed in \(O(n \log n)\) time.
 
2
Since the points in \(\mathcal{P}'_l {\setminus }\{a, b, c, d\}\) cannot affect the size of the left square, they can be pruned.
 
3
To be exact, \(\mathcal{P}_1\) (resp. \(\mathcal{P}_2\), \(\mathcal{P}_3\)) covers the first \(\lceil n/3\rceil \) (resp. next \(\lfloor n/3\rfloor \), the remaining \(\lceil n/3\rceil \) or \(\lfloor n/3\rfloor \)) points. They can be determined in linear time [2]. So the difference is at most one.
 
Literatur
1.
2.
Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448–461 (1973)CrossRefMATHMathSciNet
3.
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)CrossRefMATHMathSciNet
4.
Chandran, S., Mount, D.: A parallel algorithm for enclosed and enclosing triangles. Int. J. Comput. Geom. Appl. 2, 191–214 (1992)CrossRefMATHMathSciNet
5.
Christofides, N., Hadjiconstantinou, E.: An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. Eur. J. Oper. Res. 83(1), 21–38 (1995)CrossRefMATHMathSciNet
6.
Das, S., Goswami, P.P., Nandy, S.C.: Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation. Inform. Process. Letts. 94, 259–266 (2005)CrossRefMATHMathSciNet
7.
Hoffmann, C.M.: Robustness in geometric computations. J. Comput. Inf. Sci Eng. 1(2), 143–155 (2001)CrossRef
8.
Jaromczyk, J.W., Kowaluk, M.: Orientation independent covering of point sets \(R^{2}\) with pairs of rectangles or optimal squares. In: Proceedings of the European Workshop on Computational Geometry. LNCS, vol. 871, pp. 71–78. Springer, Heidelberg (1996)
9.
10.
Kim, S.S., Bae, S.W., Ahn, H.K.: Covering a point set by two disjoint rectangles. Int. J. Comput. Geom. Appl. 21(3), 313–330 (2011)CrossRefMATHMathSciNet
11.
12.
Mahapatra, P.R.S., Goswami, P.P., Das, S.: Covering points by isothetic unit squares. In: Proceedings of the Canadian Conference on Computational Geometry (CCCG), pp. 169–172 (2007)
13.
Mahapatra, P.R.S., Goswami, P.P., Das, S.: Maximal covering by two isothetic unit squares. In: Proceedings of the Canadian Conference on Computational Geometry (CCCG), pp. 103–106 (2008)
14.
15.
16.
O’Rourke, J., Aggarwal, A., Maddila, S., Baldwin, M.: An optimal algorithm for finding minimal enclosing triangles. J. Algorithms 7, 258–269 (1986)CrossRefMATHMathSciNet
17.
Preparata, F., Shamos, M.: Computational Geometry: An Introduction. Springer, Berlin (1990)
18.
19.
Sharir, M., Welzl, E.: Rectilinear and polygonal \(p\)-piercing and \(p\)-center problems. In: ACM Symposium on Computational Geometry, pp. 122–132 (1996)
20.
Toussaint, G.: Solving geometric problems with the rotating calipers. In: Proceedings of the IEEE MELECON (1983)
21.
Welzl, E.: Smallest enclosing disks (balls and ellipses). In: Maurer, H.A. (ed.) New Results and Trends in Computer Science. LNCS, vol. 555, pp. 359–370. Springer, Heidelberg (1991)CrossRef
Metadaten
Titel
Optimizing Squares Covering a Set of Points
verfasst von
Binay Bhattacharya
Sandip Das
Tsunehiko Kameda
Priya Ranjan Sinha Mahapatra
Zhao Song
Copyright-Jahr
2014
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-12690-6

Electronic ISBN: 978-3-319-12691-3

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-12691-3_4

Premium Partner

    Bildnachweise