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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Covering Partial Cubes with Zones Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Computational Complexity of the \(r\)-visibility Guard Set Problem for Polyominoes

verfasst von : Chuzo Iwamoto, Toshihiko Kume

Erschienen in: Discrete and Computational Geometry and Graphs

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We study the art gallery problem when the instance is a polyomino, which is the union of connected unit squares. It is shown that locating the minimum number of guards with \(r\)-visibility in a polyomino with holes is NP-hard. Here, two points \(u\) and \(v\) on a polyomino are r-visible if the orthogonal bounding rectangle for \(u\) and \(v\) lies entirely within the polyomino. As a corollary, locating the minimum number of guards with \(r\)-visibility in an orthogonal polygon with holes is NP-hard.

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 Transformability and Reversibility of Unfoldings of Doubly-Covered Polyhedra
Nächstes Kapitel Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane
Literatur
1.
Biedl, T., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: Guarding polyominoes. In: 27th Annual Symposium on Computational Geometry, pp. 387–396 (2011)
2.
Biedl, T., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: The art gallery theorem for polyominoes. Discrete Comput. Geom. 48(3), 711–720 (2012)CrossRefMATHMathSciNet
3.
Cerioli, M.R., Faria, L., Ferreira, T.O., Martinhon, C.A.J., Protti, F., Reed, B.: Partition into cliques for cubic graphs: Planar case, complexity and approximation. Discrete Appl. Math. 156(12), 2270–2278 (2008)CrossRefMATHMathSciNet
4.
Chvátal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory B. 18, 39–41 (1975)CrossRefMATH
5.
Eidenbenz, S.J., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31, 79–113 (2001)CrossRefMATHMathSciNet
6.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)MATH
7.
Hoffman, F.: On the rectilinear art gallery problem. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol. 443, pp. 717–728. Springer, Heidelberg (1990)CrossRef
8.
9.
10.
O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, New York (1987)MATH
11.
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Mass (1994)MATH
12.
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)CrossRef
13.
Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Quar. 41(2), 261–267 (1995)CrossRefMATHMathSciNet
14.
Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geom. Ap. 17(2), 105–138 (2007)CrossRefMATHMathSciNet
Metadaten
Titel
Computational Complexity of the -visibility Guard Set Problem for Polyominoes
verfasst von
Chuzo Iwamoto
Toshihiko Kume
Copyright-Jahr
2014
Buch
Discrete and Computational Geometry and Graphs

Print ISBN: 978-3-319-13286-0

Electronic ISBN: 978-3-319-13287-7

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-13287-7_8

Neuer Inhalt

    Bildnachweise