Eftersom en datauppsättning S av punkter i R 2, intervallet närmaste par (RCP) problemet syftar till att förbehandla S till en datastruktur sådan att när en frågeområde X anges, det närmaste paret i S  på X kan rapporteras effektivt. RCP-problemet kan ses som en range-search version av det klassiska närmasteparet problem, och finner applikationer i många områden. På grund av dess icke-nedbrytbarhet, RCP-problemet är mycket mer utmanande än många traditionella spektrum-sök problem. Detta dokument tar upp RCP-problemet på nytt och föreslår nya datastrukturer för olika frågetyper, inklusive kvadranter, remsor, rektanglar och halvplan. Både värsta-fall- och genomsnittsanalyser (i den meningen att datapunkterna dras jämnt och oberoende från enheten kvadrat) tillämpas på dessa nya datastrukturer, vilket resulterar i nya gränser för RCP-problemet. Vissa av de nya gränserna förbättrar avsevärt de tidigare resultaten, medan de andra är helt nya.
Toppmoderna RCP-datastrukturer för kvadrant, remsa, rektangel och halvplansfrågor gavs i det senaste arbetet REF.
New bounds for range closest-pair problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}