ข้ามไปเนื้อหา

ปัญหาไม่มีจุดสามจุดเรียงกัน

จากวิกิพีเดีย สารานุกรมเสรี


จุด 20 จุดบนกระดาน 10×10 ซึ่งไม่มีจุดสามจุดใดๆอยู่บนเส้นตรงเดียวกัน

ในทางคณิตศาสตร์ ปัญหาไม่มีจุดสามจุดเรียงกัน เป็นปัญหาที่ศึกษาเกี่ยวกับจำนวนจุดมากที่สุดที่สามารถวางในตารางขนาด n×n โดยที่ไม่มีจุดสามจุดใดๆอยู่บนเส้นตรงเดียวกัน ปัญหานี้เริ่มศึกษาโดยเฮนรี ดิวด์นีย์ ในปีพ.ศ. 2460

อ้างอิง

[แก้]
  • Dudeney, Henry (1917). Amusements in Mathematics. Edinburgh: Nelson.
  • Emilio Di Giacomo, Giuseppe Liotta, and Henk Meijer (2005). "Computing Straight-line 3D Grid Drawings of Graphs in Linear Volume". Comput. Geom. 32 (1): 26–58. doi:10.1016/j.comgeo.2004.11.003.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)
  • Vida Dujmović, Pat Morin, and David R. Wood (2005). "Layout of Graphs with Bounded Tree-Width". SIAM J. Comput. 34 (3): 553–579. doi:10.1137/S0097539702416141.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)
  • Stefan Felsner, Giussepe Liotta, and Stephen K. Wismath (2003). "Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions" (PDF). J. Graph Algorithms & Applications. 7 (4): 363–398. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2011-07-18. สืบค้นเมื่อ 2010-09-18.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)
  • Flammenkamp, Achim (1992). "Progress in the no-three-in-line problem". Journal of Combinatorial Theory, Ser. A. 60 (2): 305–311. doi:10.1016/0097-3165(92)90012-J.
  • Flammenkamp, Achim (1998). "Progress in the no-three-in-line problem, II". Journal of Combinatorial Theory, Ser. A. 81 (1): 108–113. doi:10.1006/jcta.1997.2829.
  • Guy, R. K.; Kelly, P. A. (1968). "The no-three-in-line problem". Canad. Math. Bull. 11: 527–531. MR0238765.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)
  • Hall, R. R.; Jackson, T. H.; Sudbery, A.; Wild, K. (1975). "Some advances in the no-three-in-line problem". Journal of Combinatorial Theory, Ser. A. 18: 336–341. doi:10.1016/0097-3165(75)90043-6.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)
  • Lefmann, Hanno (2008). "No l Grid-Points in spaces of small dimension". Lecture Notes in Computer Science. 5034: 259–270. doi:10.1007/978-3-540-68880-8_25.
  • Pach, János; Thiele, Torsten; Tóth, Géza (1998). "Three-dimensional grid drawings of graphs". Graph Drawing, 5th Int. Symp., GD '97. Lecture Notes in Computer Science, no. 1353, Springer-Verlag. pp. 47–51. doi:10.1007/3-540-63938-1_49.{{cite conference}}: CS1 maint: multiple names: authors list (ลิงก์)
  • Attila Pór and David R. Wood (2007). "No-three-in-line-in-3D". Algorithmica. 47: 481. doi:10.1007/s00453-006-0158-9.
  • Roth, K. F. (1951). "On a problem of Heilbronn". Journal of the London Mathematical Society. 26: 198–204. doi:10.1112/jlms/s1-26.3.198.
  • David R. Wood (2005). "Grid drawings of k-colourable graphs". Computational Geometry. 30 (1): 25–28. doi:10.1016/j.comgeo.2004.06.001.

แหล่งข้อมูลอื่น

[แก้]