Kinetic closest pair
ஒரு இயக்க நெருங்கிய ஜோடி தரவு அமைப்பு என்பது ஒரு இயக்க தரவு கட்டமைப்பாகும், இது ஒரு மெட்ரிக் இடத்தில் நேரத்துடன் தொடர்ந்து நகரும் n புள்ளிகளின் தொகுப்பு P கொடுக்கப்பட்ட மிக நெருக்கமான ஜோடி புள்ளிகளைப் பராமரிக்கிறது. நிலையான வழக்கில் பல திறமையான வழிமுறைகள் அறியப்பட்டிருந்தாலும், அவை இயக்குவதற்கு கடினமாக நிரூபிக்கப்பட்டன, எனவே இந்த சிக்கலைத் தீர்க்க புதிய நிலையான வழிமுறைகள் உருவாக்கப்பட்டன. 2டி வழக்கு அணுகுமுறை 1 மிக நெருக்கமான ஜோடியின் பராமரிப்புக்கான எளிய இயக்க அணுகுமுறை டெலவுனே முக்கோணங்களின் மாறுபாடுகளைப் பயன்படுத்துவதாகும். ஒரு அறுகோணத்தைக் கருத்தில் கொண்டு, அதை ஆறு சமபக்க முக்கோணங்களாகப் பிரித்து, பின்னர் ஒவ்வொரு சமபக்க முக்கோணத்தின் அடிப்படையில் ஒரு டெலானே முக்கோணத்தை உருவாக்குங்கள், ஏனெனில் ஒவ்வொன்றும் குவிந்த வடிவத்தில் இருக்கும். சமபக்க டெலனே வரைபடம் (ஈடிஜி) என்று அழைக்கப்படும் இந்த ஆறு டெலனே முக்கோணங்களின் ஒன்றிணைப்பு, அருகிலுள்ள அண்டை வரைபடத்திற்கான (என்என்ஜி) ஒரு சூப்பர் கிராஃப் ஆகும்; ஈடிஜியில் குறைந்தபட்ச நீளம் கொண்ட விளிம்பின் இறுதிப் புள்ளிகள் மிக நெருக்கமான ஜோடியைக் கொடுக்கின்றன. குவிந்த வடிவங்களின் அடிப்படையில் டெலானே முக்கோணங்களை பராமரிப்பது நேரடியானது. காலப்போக்கில் EDG ஐப் பொறுத்தவரை, EDG இன் விளிம்புகளில் ஒரு இயக்க போட்டி மரத்தை உருவாக்குவதன் மூலம், ஒருவர் மிக நெருக்கமான ஜோடியை எளிதாக பராமரிக்க முடியும். இந்த நெருக்கமான ஜோடி கே. டி. எஸ் திறமையானது, கடனுதவி பதிலளிக்கக்கூடியது மற்றும் கச்சிதமானது, ஆனால் பொதுவாக உள்ளூர் அல்ல. பின்வரும் அணுகுமுறை அருகிலுள்ள ஜோடியின் பராமரிப்புக்கான உள்ளூர் கே. டி. எஸ்ஸை வழங்குகிறது. அணுகுமுறை 2 இரண்டாவது இயக்க அணுகுமுறை பின்வரும் அவதானிப்புகளை அடிப்படையாகக் கொண்டது. ஒரு புள்ளியைச் சுற்றியுள்ள இடத்தை கோண ரீதியாக ஆறு "வெட்ஜ்களாக" பிரித்தால், ஒவ்வொன்றும் அகலமாக இருந்தால், ஒவ்வொரு வெட்ஜிலும் உள்ள மிக நெருக்கமான புள்ளிகளில் மிக நெருக்கமான புள்ளியாக இருக்கும். இந்தக் கட்டுரையின் எஞ்சிய பகுதி "முக்கிய" வெட்ஜ்களில் (x-அச்சால் இரண்டாகப் பிரிக்கப்பட்டவை) கவனம் செலுத்தும், மேலும் சமச்சீர் வாதங்கள் தளத்தை சுழற்றிய பிறகு மற்ற வெட்ஜ்களுக்கு பொருந்தும். பொருந்திய புள்ளிகள் புள்ளிகள் மற்றும் அவை ஒருவருக்கொருவர் நெருக்கமான புள்ளிகளாக இருந்தால் "பொருந்தியவை" என்று கூறப்படுகிறது. தெளிவாக, நெருக்கமான ஜோடி புள்ளிகள் ஒரு பொருந்திய ஜோடி. புள்ளிகள் மற்றும், இடதுபுறத்தில் உள்ளது மற்றும் மேலே விவரிக்கப்பட்ட மையத்தில் ஆப்பு உள்ளது போன்ற கருத்தில் கொள்ளுங்கள். இது மிக நெருக்கமான புள்ளியாக இருந்தால், x-திசையில் (இந்த வெட்ஜில்) மிக நெருக்கமான புள்ளியாக இருக்க வேண்டும். எனவே, x-திசையில் உள்ள மிக நெருக்கமான புள்ளிகளின் ஜோடிகளின் தொகுப்பு (இந்த வெட்ஜுக்குள்) மிக நெருக்கமான புள்ளிகளின் ஜோடிகளின் தொகுப்பின் மேற்பரப்பாகும். P தொகுப்பில் உள்ள ஒவ்வொரு புள்ளியும் p = (x, y) ஐ ஒரு புதிய புள்ளிக்கு வரைபடமாக்குங்கள், இது மாற்றப்பட்ட புள்ளிகளின் P 'தொகுப்பை உருவாக்குகிறது. ஒரு புள்ளியைப் பொறுத்தவரை, "முக்கிய" வெட்ஜ்களில் உள்ள புள்ளிகள் இந்த புதிய ஒருங்கிணைப்பு அமைப்பை விட பெரியதாகவோ அல்லது சிறியதாகவோ ஒருங்கிணைப்புகளைக் கொண்டுள்ளன என்பதை நினைவில் கொள்க. புள்ளிகளை x, u மற்றும் v ஆயத்தொகுதிகளால் வரிசைப்படுத்தி, அவற்றை இயக்க வரிசைப்படுத்தப்பட்ட பட்டியல்களில் சேமிக்கவும். உள்ள புள்ளிகளில் 2டி ரேஞ்ச் ட்ரீ டி-யை உருவாக்குங்கள். முதன்மை மரத்தில் உள்ள ஒவ்வொரு முனைக்கும், டி (டபிள்யூ) என்பது டபிள்யூ உடன் தொடர்புடைய இரண்டாம் நிலை மரமாக இருக்கட்டும். இந்த வரம்பு மரம் ஒரு புள்ளிக்கு "முக்கிய" வெட்ஜில் உள்ள புள்ளிகளை அடையாளம் காண பயன்படுத்தப்படும். முதன்மை மரத்தில் உள்ள ஒவ்வொரு முனைக்கும், மற்றும் T (w) இல் உள்ள ஒவ்வொரு முனைக்கும், ஜோடி (w, e) = (b, r) ஐக் கணக்கிடுங்கள், அங்கு b (அல்லது r) என்பது e இன் இடது (அல்லது வலது) துணை மரத்தில் அதிகபட்சம் (அல்லது குறைந்தபட்சம்) x-ஒருங்கிணைந்த புள்ளியாக வரையறுக்கப்படுகிறது. ஜோடிகளில் ஒரு இயக்க முன்னுரிமை வரிசையை உருவாக்குங்கள், முன்னுரிமைகள் ஜோடியின் புள்ளிகளுக்கு இடையிலான தூரத்தால் (அசல் ஒருங்கிணைப்பு அமைப்பில் அளவிடப்படுகிறது) தீர்மானிக்கப்படுகின்றன. முறையே இயக்க முன்னுரிமை வரிசைகளைப் பெற, விமானம் சுழற்றுவதற்கு மேலே உள்ள படிகளை மீண்டும் செய்யவும். P இல் உள்ள மிக நெருக்கமான ஜோடி புள்ளிகள் மேலே உள்ள மூன்று முன்னுரிமை வரிசைகளிலிருந்து பெறப்பட்ட குறைந்தபட்ச குறைந்தபட்சங்களுக்கு ஒத்திருக்கிறது. முன்னுரிமை வரிசைகள் மற்றும் வரிசைப்படுத்தப்பட்ட பட்டியல்களில் பராமரிப்பு சான்றிதழ் தோல்விகள் ஏற்படலாம். புள்ளிகளின் வரிசையில் இடமாற்றங்கள் டி-யில் மாற்றங்களை ஏற்படுத்தும் (இது நேரம் எடுக்கும்), மேலும் முன்னுரிமை வரிசைகளில் செருகுதல்/நீக்குதல்களை ஏற்படுத்தக்கூடும். மேலே வரையறுக்கப்பட்டுள்ளபடி தொகுப்புகளில் ஏற்படும் மாற்றங்களின் எண்ணிக்கை ஒரு நிலையான எண்ணாக இருக்க வேண்டியதில்லை என்பதை நினைவில் கொள்க. இருப்பினும், p மற்றும் q மாற்றத்தின் வரிசையின் விளைவாக பொருந்தத் தொடங்கும் அல்லது நிறுத்தப்படும் எந்த ஜோடியும் p மற்றும்/அல்லது q ஐக் கொண்டிருக்க வேண்டும், எனவே நிலையான எண்ணிக்கையிலான பொருந்தக்கூடிய ஜோடிகள் மட்டுமே உள்ளன, அவை முன்னுரிமை வரிசைகளில் செருகப்பட வேண்டும்/நீக்கப்பட வேண்டும். இந்த பொருந்திய ஜோடிகளை மட்டுமே புதுப்பிப்பது பரவாயில்லை, ஏனெனில் வரையறையின்படி, பொருந்திய ஜோடி மட்டுமே மிக நெருக்கமான ஜோடியாக இருக்க வாய்ப்பு உள்ளது. பகுப்பாய்வு இந்த கே. டி. எஸ் பின்வருமாறுஃ பதிலளிக்கக்கூடியதுஃ ஒரு நிகழ்வை செயலாக்க நேரம் எடுக்கும் உள்ளூர்ஃ ஒவ்வொரு புள்ளியும் நிலையான எண்ணிக்கையிலான இயக்க வரிசைப்படுத்தப்பட்ட பட்டியல்கள் மற்றும் இயக்க முன்னுரிமை வரிசைகளில் இருப்பதால், அந்த கட்டமைப்புகளின் இருப்பிடத்திலிருந்து இருப்பிடம் பின்தொடர்கிறது கச்சிதத்தன்மைஃ இயக்க வரிசைப்படுத்தப்பட்ட பட்டியல்கள் மற்றும் இயக்க முன்னுரிமை வரிசைகளின் சுருக்கத்திலிருந்து கச்சிதத்தன்மை பின்தொடர்கிறது திறமையானதுஃ வரிசைப்படுத்தப்பட்ட பட்டியல்களில் ஒவ்வொரு இடமாற்றமும் இயக்க முன்னுரிமை வரிசைகளில் நிலையான எண்ணிக்கையிலான செருகல்கள் மற்றும் நீக்குதல்களை ஏற்படுத்துகிறது. புள்ளிகளின் இயக்கம் போலி-இயற்கணிதமானது என்று கருதினால், ஒரு பல்லுறுப்புக்கோவை எண்ணிக்கையிலான இடமாற்றங்கள் உள்ளன, எனவே ஒரு பல்லுறுப்புக்கோவை எண்ணிக்கையிலான நிகழ்வுகள் இந்த கே. டி. எஸ் மூலம் செயலாக்கப்படுகின்றன, இது திறமையானதாக அமைகிறது இந்த அணுகுமுறையை அதிக பரிமாணங்களில் நெருக்கமான ஜோடியை பராமரிக்க பயன்படுத்தலாம். குறிப்புகள் இயக்க தரவு கட்டமைப்புகள் வடிவியல் தரவு கட்டமைப்புகள்