The Fagnano Triangle Patrolling Problem.
Saved in:
| Title: | The Fagnano Triangle Patrolling Problem. |
|---|---|
| Authors: | Georgiou, Konstantinos1, Kundu, Somnath1, Prałat, Paweł1 |
| Source: | Discrete Mathematics & Theoretical Computer Science (DMTCS). 2025, Vol. 27 Issue 3, p1-19. 19p. |
| Subjects: | Combinatorial optimization, Triangles, Time, Problem solving, Combinatorial dynamics |
| Abstract: | We investigate a combinatorial optimization problem that involves patrolling the edges of an acute triangle using a unit-speed agent. The goal is to minimize the maximum (1-gap) idle time of any edge, which is defined as the time gap between consecutive visits to that edge. This problem has roots in a centuries-old optimization problem posed by Fagnano in 1775, who sought to determine the inscribed triangle of an acute triangle with the minimum perimeter. It is well-known that the orthic triangle, giving rise to a periodic and cyclic trajectory obeying the laws of geometric optics, is the optimal solution to Fagnano’s problem. Such trajectories are known as Fagnano orbits, or more generally as billiard trajectories. We demonstrate that the orthic triangle is also an optimal solution to the patrolling problem. Our main contributions pertain to new connections between billiard trajectories and optimal patrolling schedules in combinatorial optimization. In particular, as an artifact of our arguments towards proving optimality of our results, we introduce a novel 2-gap patrolling problem that seeks to minimize the visitation time of objects every three visits. We prove that there exist infinitely many well-structured billiard-type optimal trajectories for this problem, including the orthic trajectory, which has the special property of minimizing the visitation time gap between any two consecutively visited edges. Complementary to that, we also examine the cost of dynamic, sub-optimal trajectories to the 1-gap patrolling optimization problem. These trajectories result from a greedy algorithm and can be implemented by a computationally primitive mobile agent. [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: 188966919 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: The Fagnano Triangle Patrolling Problem. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Georgiou%2C+Konstantinos%22">Georgiou, Konstantinos</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Kundu%2C+Somnath%22">Kundu, Somnath</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Prałat%2C+Paweł%22">Prałat, Paweł</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>. 2025, Vol. 27 Issue 3, p1-19. 19p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Combinatorial+optimization%22">Combinatorial optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Triangles%22">Triangles</searchLink><br /><searchLink fieldCode="DE" term="%22Time%22">Time</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+dynamics%22">Combinatorial dynamics</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We investigate a combinatorial optimization problem that involves patrolling the edges of an acute triangle using a unit-speed agent. The goal is to minimize the maximum (1-gap) idle time of any edge, which is defined as the time gap between consecutive visits to that edge. This problem has roots in a centuries-old optimization problem posed by Fagnano in 1775, who sought to determine the inscribed triangle of an acute triangle with the minimum perimeter. It is well-known that the orthic triangle, giving rise to a periodic and cyclic trajectory obeying the laws of geometric optics, is the optimal solution to Fagnano’s problem. Such trajectories are known as Fagnano orbits, or more generally as billiard trajectories. We demonstrate that the orthic triangle is also an optimal solution to the patrolling problem. Our main contributions pertain to new connections between billiard trajectories and optimal patrolling schedules in combinatorial optimization. In particular, as an artifact of our arguments towards proving optimality of our results, we introduce a novel 2-gap patrolling problem that seeks to minimize the visitation time of objects every three visits. We prove that there exist infinitely many well-structured billiard-type optimal trajectories for this problem, including the orthic trajectory, which has the special property of minimizing the visitation time gap between any two consecutively visited edges. Complementary to that, we also examine the cost of dynamic, sub-optimal trajectories to the 1-gap patrolling optimization problem. These trajectories result from a greedy algorithm and can be implemented by a computationally primitive mobile agent. [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=188966919 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 19 StartPage: 1 Subjects: – SubjectFull: Combinatorial optimization Type: general – SubjectFull: Triangles Type: general – SubjectFull: Time Type: general – SubjectFull: Problem solving Type: general – SubjectFull: Combinatorial dynamics Type: general Titles: – TitleFull: The Fagnano Triangle Patrolling Problem. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Georgiou, Konstantinos – PersonEntity: Name: NameFull: Kundu, Somnath – PersonEntity: Name: NameFull: Prałat, Paweł IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: 2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 13658050 Numbering: – Type: volume Value: 27 – Type: issue Value: 3 Titles: – TitleFull: Discrete Mathematics & Theoretical Computer Science (DMTCS) Type: main |
| ResultId | 1 |
