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

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

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

• ประเภทของวัตถุ: อัลกอริทึมจะขึ้นอยู่กับว่าSประกอบด้วยจุดเส้นส่วนของเส้นตรงกล่องรูปหลายเหลี่ยม ... หรือไม่วัตถุที่ง่ายที่สุดและมีการศึกษามากที่สุดในการค้นหาคือจุด
• ประเภทของช่วง: ช่วงการค้นหาจำเป็นต้องถูกเลือกจากชุดที่กำหนดไว้ล่วงหน้า ชุดช่วงที่ได้รับการศึกษาอย่างดีบางชุด และชื่อของปัญหาที่เกี่ยวข้อง ได้แก่สี่เหลี่ยมผืนผ้าที่วางแนวตามแกน (การค้นหาช่วงแบบตั้งฉาก) ซิ มเพ ล็กซ์ครึ่งพื้นที่และทรงกลม / วงกลม
• ประเภทของแบบสอบถาม: หากจำเป็นต้องรายงานรายการวัตถุทั้งหมดที่ตัดกับช่วงแบบสอบถาม ปัญหาดังกล่าวเรียกว่าการรายงานช่วงและแบบสอบถามนั้นเรียกว่าแบบสอบถามการรายงานบางครั้ง อาจต้องการเพียงจำนวนวัตถุที่ตัดกับช่วงเท่านั้น ในกรณีนี้ ปัญหาดังกล่าวเรียกว่าการนับช่วงและแบบสอบถามนั้นเรียกว่าแบบสอบถามการนับ แบบสอบถามความว่างเปล่าจะรายงานว่ามีวัตถุอย่างน้อยหนึ่งชิ้นที่ตัดกับช่วงหรือไม่ ในเวอร์ชันเซมิกรุป จะมีการระบุ เซมิกรุปแบบสลับที่ได้ ( S , +) แต่ละจุดจะได้รับน้ำหนักจากSและจำเป็นต้องรายงานผลรวมเซมิกรุปของน้ำหนักของจุดที่ตัดกับช่วง
• การค้นหาช่วงแบบ ไดนามิกเทียบกับการค้นหาช่วงแบบคงที่: ในการตั้งค่าแบบคงที่ ชุดSจะทราบล่วงหน้า ในการตั้งค่าแบบไดนามิก อาจมีการแทรกหรือลบวัตถุระหว่างการค้นหาได้
• การค้นหาช่วงแบบออฟไลน์: ทั้งชุดของวัตถุและชุดคำค้นหาทั้งหมดเป็นที่ทราบล่วงหน้า

ในการค้นหาช่วงแบบตั้งฉาก ชุดSประกอบด้วยจุดในมิติ และคำถามประกอบด้วยช่วงในแต่ละมิติเหล่านั้น ดังนั้น คำถามจึงประกอบด้วยสี่เหลี่ยมผืนผ้าที่จัดเรียงตามแกน หลายมิติ ด้วยขนาดเอาต์พุตJon Bentleyใช้kd tree เพื่อให้ได้ พื้นที่และเวลาในการค้นหา(ในสัญกรณ์ Big O ) ^{[ 2 ]} Bentley ยังเสนอให้ใช้range treesซึ่งปรับปรุงเวลาในการค้นหาเป็นแต่เพิ่มพื้นที่เป็น[ ^{3 ] Dan} Willardใช้ downpointers ซึ่งเป็นกรณีพิเศษของfractional cascadingเพื่อลดเวลาในการค้นหาลงอีกเป็น^{[ 4 ]}${\displaystyle n}$${\displaystyle d}$${\displaystyle k}$${\displaystyle O(n)}$${\displaystyle O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}}$${\displaystyle O(\log ^{d}n+k)}$${\displaystyle O(n\log ^{d-1}n)}$${\displaystyle O(\log ^{d-1}n+k)}$

แม้ว่าผลลัพธ์ข้างต้นจะได้รับใน แบบ จำลองเครื่องชี้แต่ก็มีการปรับปรุงเพิ่มเติมใน แบบจำลอง RAM คำสำหรับการคำนวณในมิติที่ต่ำ (2D, 3D, 4D) Bernard Chazelleใช้ต้นไม้ช่วงบีบอัดเพื่อให้ได้เวลาและพื้นที่ในการสอบถามสำหรับการนับช่วง^{[ 5 ]}ต่อมา Joseph JaJa และคนอื่นๆ ได้ปรับปรุงเวลาการสอบถามนี้สำหรับการนับช่วง ซึ่งตรงกับขอบเขตล่างและจึงเหมาะสมที่สุดในเชิง อะซิมโท ติก^{[ 6 ]}${\displaystyle O(\log n)}$${\displaystyle O(n)}$${\displaystyle O\left({\dfrac {\log n}{\log \log n}}\right)}$

ณ ปี 2015 ผลลัพธ์ที่ดีที่สุด (ในมิติที่ต่ำ (2D, 3D, 4D)) สำหรับการรายงานช่วงที่พบโดยTimothy M. Chan , Kasper Larsen และMihai Pătrașcuซึ่งใช้ต้นไม้ช่วงที่บีบอัดในแบบจำลองการคำนวณ RAM ของคำ มีดังต่อไปนี้: ^{[ 7 ]}

• ${\displaystyle O(n)}$พื้นที่, เวลาในการค้นหา${\displaystyle O(\log ^{\epsilon }n+k\log ^{\epsilon }n)}$
• ${\displaystyle O(n\log \log n)}$พื้นที่, เวลาในการค้นหา${\displaystyle O(\log \log n+k\log \log n)}$
• ${\displaystyle O(n\log ^{\epsilon }n)}$พื้นที่, เวลาในการค้นหา${\displaystyle O(\log \log n+k)}$

ในกรณีตั้งฉาก หากขอบเขตด้านใดด้านหนึ่งเป็นอนันต์การค้นหาจะเรียกว่าการค้นหาแบบสามด้าน หากขอบเขตสองด้านเป็นอนันต์ การค้นหาจะเป็นแบบสองด้าน และหากขอบเขตด้านใดด้านหนึ่งไม่เป็นอนันต์ การค้นหาจะเป็นแบบสี่ด้าน

ในขณะที่การค้นหาช่วงคงที่นั้นทราบเซตSล่วงหน้า แต่ การค้นหาช่วง ไดนามิกนั้นอนุญาตให้มีการแทรกและลบจุดได้ ในเวอร์ชันแบบเพิ่มขึ้นของปัญหา อนุญาตให้มีการแทรกเท่านั้น ในขณะที่เวอร์ชันแบบลดลงอนุญาตให้มีการลบเท่านั้น สำหรับกรณีตั้งฉากKurt Mehlhornและ Stefan Näher ได้สร้างโครงสร้างข้อมูลสำหรับการค้นหาช่วงไดนามิกซึ่งใช้ การ เรียงลำดับเศษส่วนแบบไดนามิกเพื่อให้ได้พื้นที่และเวลาในการค้นหา^{[ 8 ]}ทั้งเวอร์ชันแบบเพิ่มขึ้นและแบบลดลงของปัญหาสามารถแก้ไขได้ด้วยเวลาในการค้นหา แต่ยังไม่ทราบว่าการค้นหาช่วงไดนามิกทั่วไปสามารถทำได้ด้วยเวลาในการค้นหานั้นหรือไม่ ${\displaystyle O(n\log n)}$${\displaystyle O(\log n\log \log n+k)}$${\displaystyle O(\log n+k)}$

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

นอกจากจะนำมาพิจารณาในเรขาคณิตเชิงคำนวณแล้ว การค้นหาช่วง และโดยเฉพาะอย่างยิ่งการค้นหาช่วงแบบตั้งฉาก ยังมีการประยุกต์ใช้สำหรับการสอบถามช่วงในฐานข้อมูลอีกด้วย การค้นหาช่วงแบบใช้สีก็ถูกนำมาใช้และได้รับแรงบันดาลใจจากการค้นหาข้อมูลเชิงหมวดหมู่ ตัวอย่างเช่น การหาแถวในฐานข้อมูลบัญชีธนาคารที่แสดงถึงบุคคลที่มีอายุระหว่าง 25 ถึง 40 ปี และมีเงินระหว่าง 10,000 ถึง 20,000 ดอลลาร์ อาจเป็นปัญหาการรายงานช่วงแบบตั้งฉาก โดยที่อายุและเงินเป็นสองมิติ

• ต้นไม้ในเขต
• การค้นหาช่วง

• เดอ เบิร์ก, มาร์ก; ฟาน เครเวลด์, มาร์ก; โอเวอร์มาร์ส, มาร์ก ; Schwarzkopf, Otfried (2000), Computational Geometry (ฉบับพิมพ์ครั้งที่ 2), เบอร์ลิน: Springer-Verlag, ISBN 3-540-65620-0
• Matoušek, Jiří (1994), "Geometric range search" , ACM Computing Surveys , 26 (4): 421– 461, doi : 10.1145/197405.197408 , S2CID  17729301.