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

ในรูปแบบทั่วไปรูปแบบหนึ่ง ปัญหาคือ เมื่อกำหนดพื้นที่แบ่งออกเป็น ส่วนๆ ที่ไม่ทับซ้อนกันแล้วจะต้องระบุพื้นที่ที่จุดสอบถามอยู่ ตัวอย่างเช่น ปัญหาในการระบุหน้าต่างใดของอินเทอร์เฟซผู้ใช้แบบกราฟิกที่มีการคลิกเมาส์ที่กำหนด สามารถกำหนดเป็นกรณีของการระบุตำแหน่งจุดได้ โดยมีการแบ่งย่อยที่เกิดจากส่วนที่มองเห็นได้ของแต่ละหน้าต่าง แม้ว่าโครงสร้างข้อมูลเฉพาะทางอาจเหมาะสมกว่าโครงสร้างข้อมูลการระบุตำแหน่งจุดทั่วไปในแอปพลิเคชันนี้ก็ตาม^{[ 1 ]}กรณีพิเศษคือ ปัญหา จุดในรูปหลายเหลี่ยมซึ่งจำเป็นต้องระบุว่าจุดนั้นอยู่ภายใน ภายนอก หรือบนขอบของรูปหลายเหลี่ยม เดียว หรือไม่ นอกจากนี้ยังมีกรณีพิเศษอื่นๆ อีกด้วย

ปัญหาดังกล่าวอาจกล่าวได้สำหรับกลุ่มของบริเวณใดๆ ในอวกาศ ซึ่งไม่จำเป็นต้องแยกจากกันโดยสิ้นเชิงและไม่จำเป็นต้องประกอบกันเป็นพาร์ทิชัน

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

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

โครงสร้างข้อมูลที่ง่ายที่สุดและเก่าแก่ที่สุดที่ทำให้ได้เวลา O(log n ) ถูกค้นพบโดยDobkinและLiptonในปี 1976 โดยอาศัยการแบ่งS ออกเป็นส่วน ย่อยโดยใช้เส้นแนวตั้งที่ผ่านจุดยอดแต่ละจุดในSบริเวณระหว่างเส้นแนวตั้งสองเส้นที่อยู่ติดกันเรียกว่าแผ่น (slab ) โปรดสังเกตว่าแต่ละแผ่นถูกแบ่งออกโดยส่วนของเส้นตรงที่ไม่ตัดกันซึ่งตัดผ่านแผ่นจากซ้ายไปขวาอย่างสมบูรณ์ บริเวณระหว่างส่วนของเส้นตรงสองส่วนที่อยู่ติดกันภายในแผ่นจะสอดคล้องกับหน้าเฉพาะของSดังนั้น เราจึงลดปัญหาการระบุตำแหน่งจุดของเราให้เหลือปัญหาที่ง่ายกว่าสองปัญหา: ^{[ 2 ]}

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

ปัญหาแรกสามารถแก้ไขได้โดยการค้นหาแบบไบนารีบน พิกัด xของเส้นแนวตั้งในเวลา O(log n ) ปัญหาที่สองก็สามารถแก้ไขได้ในเวลา O(log n ) โดยการค้นหาแบบไบนารีเช่นกัน เพื่อดูว่าทำได้อย่างไร โปรดสังเกตว่า เนื่องจากส่วนต่างๆ ไม่ตัดกันและข้ามแผ่นอย่างสมบูรณ์ ส่วนต่างๆ จึงสามารถเรียงลำดับตามแนวตั้งภายในแต่ละแผ่นได้ แม้ว่าอัลกอริทึมนี้จะช่วยให้สามารถระบุตำแหน่งจุดได้ในเวลาลอการิทึมและง่ายต่อการใช้งาน แต่พื้นที่ที่จำเป็นในการสร้างแผ่นและบริเวณที่บรรจุอยู่ภายในแผ่นอาจสูงถึง O( n² ) เนื่องจากแต่ละแผ่นอาจตัดผ่านส่วนต่างๆ จำนวนมาก^{[ 2 ]}

ผู้เขียนหลายคนสังเกตเห็นว่าส่วนที่ตัดผ่านแผ่นสองแผ่นที่อยู่ติดกันส่วนใหญ่จะเหมือนกัน ดังนั้นขนาดของโครงสร้างข้อมูลจึงสามารถลดลงได้อย่างมาก โดยเฉพาะอย่างยิ่ง Sarnak และ Tarjan กวาดเส้นแนวตั้งlจากซ้ายไปขวาบนระนาบ ในขณะที่ยังคงรักษาส่วนที่ตัดกับl ไว้ ในต้นไม้แดงดำถาวร ซึ่งช่วยให้พวกเขาลดพื้นที่จัดเก็บลงเหลือ O( n ) ในขณะที่ยังคงรักษาเวลาการค้นหา O(log n ) ไว้ ^{[ 3 ]}

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

จุดอ่อนของการแบ่งส่วนแผ่นคือเส้นแนวตั้งสร้างส่วนย่อยเพิ่มเติมในการแบ่งส่วน ทำให้ยากที่จะบรรลุพื้นที่จัดเก็บ O( n ) Herbert Edelsbrunner , Leonidas J. GuibasและJorge Stolfiค้นพบโครงสร้างข้อมูลที่เหมาะสมที่สุดซึ่งใช้เฉพาะขอบในการแบ่งย่อยแบบโมโนโทน แนวคิดคือการใช้โซ่โมโนโทนแนวตั้ง แทนที่จะใช้เส้นแนวตั้งเพื่อแบ่งส่วนย่อย^{[ 4 ​​]}

การแปลงแนวคิดทั่วไปนี้ให้เป็นโครงสร้างข้อมูลที่มีประสิทธิภาพจริงนั้นไม่ใช่เรื่องง่าย ประการแรก เราต้องสามารถคำนวณโซ่โมโนโทนที่แบ่งส่วนย่อยออกเป็นสองส่วนที่มีขนาดใกล้เคียงกัน ประการที่สอง เนื่องจากขอบบางส่วนอาจอยู่ในโซ่โมโนโทนหลายเส้น เราจึงต้องระมัดระวังเพื่อให้แน่ใจว่าพื้นที่จัดเก็บเป็น O(n) ประการที่สาม การทดสอบว่าจุดอยู่ทางด้านซ้ายหรือด้านขวาของส่วนย่อยโมโนโทนใช้เวลา O( n ) หากดำเนินการอย่างง่ายๆ^{[ 4 ]}

รายละเอียดเกี่ยวกับวิธีการแก้ปัญหาสองข้อแรกนั้นอยู่นอกเหนือขอบเขตของบทความนี้ เราจะกล่าวถึงวิธีการแก้ไขปัญหาข้อที่สามโดยสังเขป การใช้การค้นหาแบบไบนารี เราสามารถทดสอบได้ว่าจุดนั้นอยู่ทางซ้ายหรือขวาของโซ่โมโนโทนในเวลา O(log n ) เนื่องจากเราต้องทำการค้นหาแบบไบนารีซ้อนกันอีกครั้งผ่านโซ่ O(log n ) เพื่อกำหนดตำแหน่งของจุดจริง ๆ เวลาในการค้นหาจึงเป็น O(log² n) เพื่อให้ได้เวลาในการค้นหา O(log n ) เราต้องใช้การเรียงลำดับแบบเศษส่วนโดยเก็บตัวชี้ระหว่างขอบของโซ่โมโนโทนที่แตกต่างกัน^{[ 4 ]}

รูปหลายเหลี่ยมที่มีmจุดยอดสามารถแบ่งออกเป็นm –2 สามเหลี่ยม ซึ่งสามารถแสดงได้โดยการอุปมานเริ่มต้นจากสามเหลี่ยม มีอัลกอริทึมมากมายในการแบ่งรูปหลายเหลี่ยมออกเป็นรูปสามเหลี่ยมอย่างมีประสิทธิภาพ โดยวิธีที่เร็วที่สุดมีเวลาในกรณีที่เลวร้ายที่สุดคือ O( n ) ดังนั้น เราจึงสามารถแบ่งรูปหลายเหลี่ยมแต่ละรูปของการแบ่งย่อยของเราออกเป็นรูปสามเหลี่ยม และจำกัดโครงสร้างข้อมูลของเราไว้เฉพาะกรณีของการแบ่งย่อยที่เกิดจากรูปสามเหลี่ยมเท่านั้น Kirkpatrick ได้นำเสนอโครงสร้างข้อมูลสำหรับตำแหน่งจุดในการแบ่งย่อยที่เป็นรูปสามเหลี่ยมด้วยพื้นที่จัดเก็บ O( n ) และเวลาในการค้นหา O(log n ) ^{[ 5 ]}

แนวคิดทั่วไปคือการสร้างลำดับชั้นของรูปสามเหลี่ยม เพื่อทำการค้นหา เราเริ่มต้นด้วยการค้นหารูปสามเหลี่ยมระดับบนสุดที่ประกอบด้วยจุดค้นหา เนื่องจากจำนวนรูปสามเหลี่ยมระดับบนสุดมีขอบเขตจำกัดด้วยค่าคงที่ การดำเนินการนี้จึงสามารถทำได้ในเวลา O(1) รูปสามเหลี่ยมแต่ละรูปมีตัวชี้ไปยังรูปสามเหลี่ยมที่มันตัดกันในระดับถัดไปของลำดับชั้น และจำนวนตัวชี้ก็มีขอบเขตจำกัดด้วยค่าคงที่เช่นกัน เราดำเนินการค้นหาโดยการค้นหาว่ารูปสามเหลี่ยมใดประกอบด้วยจุดค้นหาในแต่ละระดับ^{[ 5 ]}

โครงสร้างข้อมูลถูกสร้างขึ้นในลำดับตรงกันข้าม นั่นคือจากล่างขึ้นบน เราเริ่มต้นด้วยการแบ่งย่อยแบบสามเหลี่ยม และเลือกเซตอิสระของจุดยอดที่จะถูกลบออก หลังจากลบจุดยอดแล้ว เราจะแบ่งย่อยแบบสามเหลี่ยมอีกครั้ง เนื่องจากการแบ่งย่อยเกิดจากรูปสามเหลี่ยม อัลกอริทึมแบบโลภสามารถค้นหาเซตอิสระที่มีจุดยอดเป็นสัดส่วนคงที่ได้ ดังนั้นจำนวนขั้นตอนการลบจึงเป็น O(log n ) ^{[ 5 ]}

แนวทางแบบสุ่มสำหรับปัญหานี้ขึ้นอยู่กับการแบ่งส่วนแบบสี่เหลี่ยมคางหมูหรือแผนที่สี่เหลี่ยมคางหมู การแบ่งส่วนแบบสี่เหลี่ยมคางหมูได้มาจากการยิงกระสุนแนวตั้งขึ้นและลงจากแต่ละจุดยอดในการแบ่งย่อยเดิม กระสุนจะหยุดเมื่อกระทบกับขอบ และสร้างขอบใหม่ในการแบ่งย่อย ด้วยวิธีนี้ เราจะได้เซตย่อยของการแบ่งส่วนแผ่น โดยมีเพียง O( n ) ขอบและจุดยอด เนื่องจากสำหรับแต่ละจุดยอดในการแบ่งย่อยเดิม เราจะเพิ่มจุดยอดใหม่เพียงสองจุดและเพิ่มจำนวนขอบขึ้นสี่จุดเท่านั้น^{[ 6 ]}

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

การกำหนดตำแหน่งจุดในส่วนย่อยปัจจุบันที่ดำเนินการภายในอัลกอริทึมนี้ อาจทำได้โดยใช้โครงสร้างเดียวกันกับที่ใช้สำหรับการค้นหาตำแหน่งจุดในการแบ่งรูปสี่เหลี่ยมคางหมูขั้นสุดท้ายเมื่อสิ้นสุดอัลกอริทึม โครงสร้างข้อมูลตำแหน่งจุดนี้อยู่ในรูปของกราฟแบบมีทิศทางและไม่มีวงจร โดยที่จุดยอดคือรูปสี่เหลี่ยมคางหมูที่มีอยู่ ณ จุดใดจุดหนึ่งในการปรับปรุง และขอบแบบมีทิศทางเชื่อมต่อรูปสี่เหลี่ยมคางหมูแต่ละรูปที่ไม่อยู่ในการปรับปรุงแล้วกับรูปสี่เหลี่ยมคางหมูที่เข้ามาแทนที่ การค้นหาตำแหน่งจุดทำได้โดยการติดตามเส้นทางในกราฟนี้ เริ่มต้นจากรูปสี่เหลี่ยมคางหมูเริ่มต้น และในแต่ละขั้นตอนจะเลือกรูปสี่เหลี่ยมคางหมูที่เข้ามาแทนที่ซึ่งมีจุดที่ต้องการค้นหา จนกว่าจะถึงรูปสี่เหลี่ยมคางหมูที่ยังไม่ถูกแทนที่ ความลึกโดยเฉลี่ยของการค้นหาในกราฟแบบมีทิศทางนี้ เริ่มต้นจากจุดที่ต้องการค้นหาใดๆ คือ O(log n ) พื้นที่สำหรับโครงสร้างข้อมูลเป็นสัดส่วนกับจำนวนรูปสี่เหลี่ยมคางหมูที่สร้างขึ้นตลอดกระบวนการปรับปรุงนี้ ซึ่งโดยเฉลี่ยแล้วคือ O( n ) ^{[ 6 ]}

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

ในพื้นที่สามมิติ สามารถตอบคำถามเกี่ยวกับตำแหน่งจุดได้ในเวลา O(log² n ) โดยใช้ พื้นที่O( n log n ) แนวคิดทั่วไปคือการรักษาโครงสร้างข้อมูลตำแหน่งจุดระนาบหลายโครงสร้าง ซึ่งสอดคล้องกับจุดตัดของการแบ่งย่อยกับระนาบขนาน nระนาบที่บรรจุจุดยอดของการแบ่งย่อยแต่ละจุด การใช้แนวคิดนี้อย่างง่ายๆ จะทำให้พื้นที่จัดเก็บเพิ่มขึ้นเป็น O( n ² ) ในทำนองเดียวกันกับการแบ่งส่วนแผ่น ความคล้ายคลึงกันระหว่างโครงสร้างข้อมูลที่ต่อเนื่องกันสามารถนำมาใช้เพื่อลดพื้นที่จัดเก็บเป็น O( n log n ) แต่เวลาในการสอบถามจะเพิ่มขึ้นเป็น O(log² n ) ^{[ 7 ]}

ใน ปริภูมิ dมิติ การหาตำแหน่งของจุดสามารถทำได้โดยการฉายภาพหน้าต่างๆ ซ้ำๆ ลงในปริภูมิ ( d - 1) มิติ ในขณะที่เวลาในการค้นหาคือ O(log n ) พื้นที่จัดเก็บอาจสูงถึงความซับซ้อนสูงของ โครงสร้างข้อมูล dมิติ นำไปสู่การศึกษาเกี่ยวกับการแบ่งย่อยประเภทพิเศษ ${\displaystyle O(n^{2^{d}})}$

ตัวอย่างที่สำคัญอย่างหนึ่งคือกรณีของการจัดเรียงไฮเปอร์เพลนการจัดเรียง ไฮเปอร์เพลนจำนวน nระนาบจะกำหนดเซลล์จำนวน O( n ^d ) เซลล์ แต่การระบุตำแหน่งจุดสามารถทำได้ในเวลา O(log n ) โดยใช้พื้นที่ O( n ^d ) โดย ใช้การตัดแบบลำดับชั้นของChazelle

การแบ่งย่อยแบบพิเศษอีกประเภทหนึ่งเรียกว่าการแบ่งย่อยแบบเส้นตรง (หรือแบบตั้งฉาก) ในการแบ่งย่อยแบบเส้นตรง ขอบทั้งหมดจะขนานกับแกนตั้งฉากแกนใดแกนหนึ่งdแกน ในกรณีนี้ การหาตำแหน่งของจุดสามารถทำได้ในเวลา O(log ^{d -1} n ) โดยใช้ พื้นที่ O( n )

• คลังข้อมูลจุด-ตำแหน่งที่มหาวิทยาลัยสโตนีบรูก
• การค้นหาตำแหน่งจุดในCGALซึ่งเป็นไลบรารีอัลกอริธึมทางเรขาคณิตเชิงคำนวณ