ในตอนที่ผ่านมาเราได้เห็นอัลกอริทึมสำหรับการค้นหาบนพิสัยแบบ 1 มิติไปแล้ว คราวนี้เราจะมาพิจารณาปัญหาในมิติที่สูงขึ้นไป โดยเราจะมองผ่านกรณี 2 มิติเป็นตัวอย่างประกอบ อย่างไรก็ตาม ในภาพรวมแล้วเทคนิคอัลกอริทึมที่กำลังนำเสนอนี้สามารถถูกนำไปประยุกต์ใช้กับมิติใดๆ ก็ได้ (เพียงแค่ว่าในรายละเอียดแล้วเราจะได้ค่าความซับซ้อนแย่ลง)

หนึ่งในคำถามสุดคลาสสิกในเรขาคณิตเชิงคำนวณ เริ่มจากให้ข้อมูลตั้งต้นที่ประกอบด้วยจุด $n$ จุดบนระนาบ เราจะถามว่า ภายในพิสัย (range) ที่เราสนใจนั้นมีจุดใดปรากฏตัวขึ้นมาบ้าง?

ความน่าตื่นตาตื่นใจของเรขาคณิตวิเคราะห์ที่ชาวกรีกโบราณน่าจะไม่มีวันคาดคิดถึง (เพราะสมัยนั้นยังไม่ได้ประดิษฐ์ระบบพิกัดคาร์ทีเซียนมาใช้งาน) คงหนีไม่พ้นแนวคิดทวิภาวะ (duality)¹ ระหว่างจุดกับเส้นตรง ซึ่งก็คือ เริ่มจากเรามีจุด $p$ และเส้นตรง $\ell$ ที่นิยามผ่านสมการพิกัดว่า

จบไปแล้วอีกปีกับงานบาร์แคมป์บางเขน ซึ่งเอาจริงก็นับว่าเป็นบาร์แคมป์ที่สนุกมากทีเดียว แม้ว่างานช่วงเช้าจะดูอ๊องๆ เงียบเหงาคนน้อยไปหน่อยก็ตาม

เรือใบนั้นเป็นเทคโนโลยีที่อยู่เคียงข้างมนุษยชาตินับพันปี ตั้งแต่ชาวโพลินีเซียที่แล่นเรือค้นพบหมู่เกาะในแปซิฟิค ชาวไวกิงกับเรือยาวอันน่าเกรงขาม กองเรือของเจิ้งเหอที่ส่งให้จีนเป็นมหาอำนาจ มาจนถึงยุคทองของการสำรวจที่ชาติต่างๆ ในยุโรปต่างแข่งขันกันเดินเรือเพื่อพิสูจน์ว่าโลกกลม

Last week I stumbled upon a nice little math problem: given a set of $n$ integers, show that there exists a nonempty subset $V \subseteq \lbrace v_1,v_2,\dots,v_n \rbrace$ such that $\sum V \equiv 0 \pmod{n}$.

It’s almost a coincidence that

The Voronoi diagram is a powerful geometric structure with numerous applications. In two-dimensional space $\mathbb{R}^2$, it represents a subdivision of the plane based on given initial seeds. In this session, we are interested in the computational aspect of the diagram. Specifically, we will delve into an efficient algorithm proposed by Fortune in 1986. Although the original algorithm can be challenging to comprehend, we will explore a geometric interpretation that casts the problem in three-dimensional space $\mathbb{R}^3$. This perspective offers a more intuitive understanding of the problem and unveils an intriguing connection to conic sections.

สงสัยมานานแล้วว่า ในโลกความจริงเนี่ย ธนาคารเค้าคิดดอกเบี้ยกันยังไง อย่างเช่น “ดอกเบี้ย 100% ต่อปี” (ขอเริ่มด้วยเลขที่ไม่ตรงกับโลกจริงไปก่อน) ก็แปลว่าถ้าเราฝากเงินตั้งแต่ต้นปีไปจนจบปี เราจะได้เงินเพิ่มขึ้นมาอีกหนึ่งเท่าตัว (รวมเป็นมีเงิน 2 เท่าของเงินตั้งต้น)

เพิ่งรู้ว่าสาวจีนเวลาจะเข้าไปทักจีบผช เค้าจะแตะๆ ที่แขนแล้วถามว่าเสื้อตัวนี้ซื้อที่ไหน ถถถถถถถถ