View in EDS PDF Full Text

Sometimes Two Irrational Guards are Needed.

Saved in:
Bibliographic Details
Title: Sometimes Two Irrational Guards are Needed.
Authors: Meijer, Lucas1, Miltzow, Tillmann1
Source: Discrete Mathematics & Theoretical Computer Science (DMTCS). 2026, Vol. 28 Issue 2, p1-24. 24p.
Subjects: Computational geometry, Rational points (Geometry)
Abstract: In the art gallery problem, we are given a closed polygon P, with rational coordinates and an integer k. We are asked whether it is possible to find a set (of guards) G of size k such that any point p ∈ P is seen by a point in G. We say two points p, q see each other if the line segment pq is contained inside P. It was shown by Abrahamsen, Adamaszek, and Miltzow that there is a polygon that can be guarded with three guards, but requires four guards if the guards are required to have rational coordinates. In other words, an optimal solution of size three might need to be irrational. We show that an optimal solution of size two might need to be irrational. Note that it is well-known that any polygon that can be guarded with one guard has an optimal guard placement with rational coordinates. Hence, our work closes the gap on when irrational guards are possible to occur. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 193021513
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Sometimes Two Irrational Guards are Needed.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Meijer%2C+Lucas%22">Meijer, Lucas</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Miltzow%2C+Tillmann%22">Miltzow, Tillmann</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Mathematics+%26+Theoretical+Computer+Science+%28DMTCS%29%22">Discrete Mathematics & Theoretical Computer Science (DMTCS)</searchLink>. 2026, Vol. 28 Issue 2, p1-24. 24p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Rational+points+%28Geometry%29%22">Rational points (Geometry)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In the art gallery problem, we are given a closed polygon P, with rational coordinates and an integer k. We are asked whether it is possible to find a set (of guards) G of size k such that any point p ∈ P is seen by a point in G. We say two points p, q see each other if the line segment pq is contained inside P. It was shown by Abrahamsen, Adamaszek, and Miltzow that there is a polygon that can be guarded with three guards, but requires four guards if the guards are required to have rational coordinates. In other words, an optimal solution of size three might need to be irrational. We show that an optimal solution of size two might need to be irrational. Note that it is well-known that any polygon that can be guarded with one guard has an optimal guard placement with rational coordinates. Hence, our work closes the gap on when irrational guards are possible to occur. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=193021513
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 24
        StartPage: 1
    Subjects:
      – SubjectFull: Computational geometry
        Type: general
      – SubjectFull: Rational points (Geometry)
        Type: general
    Titles:
      – TitleFull: Sometimes Two Irrational Guards are Needed.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Meijer, Lucas
      – PersonEntity:
          Name:
            NameFull: Miltzow, Tillmann
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: 2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 13658050
          Numbering:
            – Type: volume
              Value: 28
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Discrete Mathematics & Theoretical Computer Science (DMTCS)
              Type: main
ResultId 1