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

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

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

อัลกอริทึมแบบสุ่มเชิง เส้น ที่ คาดหวังเวลาของRabin (1976)ซึ่งได้รับการดัดแปลงเล็กน้อยโดยRichard Liptonเพื่อให้การวิเคราะห์ง่ายขึ้น ดำเนินการดังต่อไปนี้ บนชุดข้อมูลนำเข้าที่ประกอบด้วยจุดในปริภูมิยุคลิดมิติ: ${\displaystyle S}$${\displaystyle n}$${\displaystyle k}$

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

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

แต่ในทางกลับกัน อัลกอริทึมที่แตกต่างออกไปของKhuller & Matias (1995)ประกอบด้วยสองขั้นตอน: กระบวนการกรองแบบวนซ้ำแบบสุ่มที่ประมาณระยะทางที่ใกล้ที่สุดภายในอัตราส่วนการประมาณค่าพร้อมกับขั้นตอนสุดท้ายที่เปลี่ยนระยะทางโดยประมาณนี้ให้เป็นระยะทางที่ใกล้ที่สุดที่แน่นอน กระบวนการกรองจะทำซ้ำขั้นตอนต่อไปนี้ จนกว่าจะว่างเปล่า: ${\displaystyle 2{\sqrt {k}}}$${\displaystyle S}$

1. เลือกจุดหนึ่งแบบสุ่มอย่างสม่ำเสมอจากกลุ่มจุดทั้งหมด${\displaystyle p}$${\displaystyle S}$
2. คำนวณระยะทางจากจุดหนึ่งไปยังจุดอื่นๆ ทั้งหมดในและให้เป็นระยะทางต่ำสุดดังกล่าว${\displaystyle p}$${\displaystyle S}$${\displaystyle d}$
3. ปรับจุดข้อมูลนำเข้าให้เป็นตารางสี่เหลี่ยมขนาดและลบจุดทั้งหมด ที่ ไม่มีจุดอื่นอยู่ในบริเวณใกล้เคียงแบบมัวร์${\displaystyle d/(2{\sqrt {k}})}$${\displaystyle S}$

ระยะทางโดยประมาณที่พบโดยกระบวนการกรองนี้คือค่าสุดท้ายของ ซึ่งคำนวณในขั้นตอนก่อนที่ จะว่างเปล่า แต่ละขั้นตอนจะลบจุดทั้งหมดที่มีเพื่อนบ้านที่ใกล้ที่สุดอยู่ที่ระยะทางหรือมากกว่า อย่างน้อยครึ่งหนึ่งของจุดโดยเฉลี่ย ซึ่งส่งผลให้เวลาที่คาดหวังทั้งหมดสำหรับการกรองเป็นเชิงเส้น เมื่อทราบค่าโดยประมาณของ แล้ว สามารถนำไปใช้ในขั้นตอนสุดท้ายของอัลกอริทึมของ Rabin ได้ ในขั้นตอนเหล่านี้ จุดกริดแต่ละจุดจะมีจำนวนอินพุตคงที่ที่ปัดเศษเป็นค่าของมัน ดังนั้นเวลาจึงเป็นเชิงเส้นอีกครั้ง^{[ 3 ]}${\displaystyle d}$${\displaystyle S}$${\displaystyle d}$${\displaystyle d}$

รูปแบบไดนามิกของปัญหาการจับคู่ที่ใกล้ที่สุดมีรายละเอียดดังนี้:

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

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

อัลกอริทึมสำหรับปัญหาคู่ที่ใกล้ที่สุดแบบไดนามิกในพื้นที่มิติได้รับการพัฒนาโดย Sergey Bespamyatnikh ในปี 1998 ^{[ 10 ]}สามารถแทรกและลบจุดได้ในเวลาต่อจุด (ในกรณีที่เลวร้ายที่สุด) ${\displaystyle d}$${\displaystyle O(\log n)}$

• ระบบสารสนเทศภูมิศาสตร์ (GIS)
• การค้นหาเพื่อนบ้านที่ใกล้ที่สุด