پیوندهای مفید
آمار
| تعداد نشریات | 8 |
| تعداد شماره‌ها | 419 |
| تعداد مقالات | 5,516 |
| تعداد مشاهده مقاله | 6,268,261 |
| تعداد دریافت فایل اصل مقاله | 5,426,861 |
Counting closed billiard paths | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 5، دوره 1، شماره 2، آذر 2020، صفحه 171-177 اصل مقاله (485.13 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2020.17320.1026 | ||
| نویسندگان | ||
| Zahed Rahmati* 1؛ Sina Farahzad1؛ Ali Rahmati2 | ||
| 1Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran | ||
| 2Malek-Ashtar University of Technology, Tehran, Iran | ||
| چکیده | ||
| Given a pool table enclosing a set of axis-aligned rectangles, with a total of n edges, this paper studies $\it{closed~billiard~paths}$. A closed billiard path is formed by following the ball shooting from a starting point into some direction, such that it doesn’t touch any corner of a rectangle, doesn’t visit any point on the table twice, and stops exactly at the starting position. The $\it{signature}$ of a billiard path is the sequence of the labels of edges in the order that are touched by the path, while repeated edge reflections like $abab$ are replaced by $ab$. We prove that the length of a signature is at most $4.5n−9$, and we show that there exists an arrangement of rectangles where the length of the signature is $1.25n+2$. We also prove that the number of distinct signatures for fixed shooting direction ($45^{\circ}$) is at most $1.5n−6$. | ||
| کلیدواژه‌ها | ||
| Billiard paths؛ Maximum path length؛ Computational geometry | ||
| مراجع | ||
|
[1] d. B. Mark, C. Otfried, v. K. Marc, and O. Mark, Computational geometry algorithms and applications, Spinger, 2008.
[2] J. O’Rourke, Open problems from CCCG 2017, in Proceedings of the 30th Annual Canadian Conference on Computational Geometry, CCCG 2018, Winnipeg, Canada, 2018, Computer Science: Faculty Publications, Smith College, Northampton, MA, pp. 149–154.
[3] d. B. Mark, C. Otfried, v. K. Marc, and O. Mark, Computational geometry algorithms and applications, Spinger, 2008.
[4] [2] J. O’Rourke, Open problems from CCCG 2017, in Proceedings of the 30th Annual Canadian Conference on Computational Geometry, CCCG 2018, Winnipeg, Canada, 2018, Computer Science: Faculty Publications, Smith College, Northampton, MA, pp. 149–154. | ||
|
آمار تعداد مشاهده مقاله: 1,686 تعداد دریافت فایل اصل مقاله: 881 |
||