Kinetic convex hull
ஒரு இயக்க குவிந்த மேலோடு தரவு அமைப்பு என்பது ஒரு இயக்க தரவு அமைப்பு ஆகும், இது தொடர்ந்து நகரும் புள்ளிகளின் தொகுப்பின் குவிந்த மேலோடு பராமரிக்கிறது. இது மாறும் குவிந்த மேலோடு தரவு கட்டமைப்புகளிலிருந்து வேறுபடுத்தப்பட வேண்டும், அவை தொடர்ச்சியான இயக்கத்தை விட புள்ளிகளை செருகுதல் அல்லது நீக்குதல் போன்ற தனித்துவமான மாற்றங்களுக்கு உட்படும் புள்ளிகளைக் கையாளுகின்றன. 2டி வழக்கு 2 பரிமாண கைனெட்டிக் குவிந்த ஹல் சிக்கலுக்கான சிறந்த அறியப்பட்ட தரவு அமைப்பு பாஸ்ச், குய்பாஸ் மற்றும் ஹெர்ஷ்பெர்கர் ஆகியோரால் உருவாக்கப்பட்டது. இந்த தரவு அமைப்பு பதிலளிக்கக்கூடிய, திறமையான, கச்சிதமான மற்றும் உள்ளூர். தரவு அமைப்பு புள்ளிகளின் தொகுப்பின் குவிந்த மேலோட்டத்தின் இரட்டை என்பது இரட்டைக் கோடுகளின் மேல் மற்றும் கீழ் உறைகள் ஆகும். எனவே, நகரும் கோடுகளின் தொகுப்பின் மேல் மற்றும் கீழ் உறைகளை பராமரிப்பது நகரும் புள்ளிகளின் தொகுப்பின் குவிந்த மேலோட்டத்தை பராமரிப்பதற்கு சமம். மேல் மற்றும் கீழ் உறைகளை கணக்கிடுவது சமமான சிக்கல்கள், எனவே கோடுகளின் தொகுப்பின் மேல் உறையை கணக்கிடுவது நகரும் புள்ளிகளின் தொகுப்பின் குவிந்த மேலோட்டத்தை கணக்கிடுவதற்கு சமம். நிலையான கோடுகளின் தொகுப்பின் மேல் உறை ஒரு வகுத்தல் மற்றும் வெற்றி வழிமுறையைப் பயன்படுத்தி கணக்கிடப்படலாம், இது கோடுகளை சம அளவிலான இரண்டு தொகுப்புகளாகப் பிரிக்கிறது, அவற்றின் மேல் உறைகளைக் கண்டறிய இரண்டு தொகுப்புகளில் தன்னை மீண்டும் மீண்டும் அழைக்கிறது, பின்னர் இதன் விளைவாக வரும் இரண்டு மேல் உறைகளையும் இணைக்கிறது. ஒரு செங்குத்து கோடு ஸ்வீப்பைப் பயன்படுத்தி இணைக்கும் படி செய்யப்படுகிறது. புள்ளிகளின் முதல் தொகுப்பை நீல நிறமாகவும், இரண்டாவது தொகுப்பை சிவப்பு நிறமாகவும் அழைக்கவும். மேல் உறைகளை இணைப்பதற்கான நிலையான லைன் ஸ்வீப் வழிமுறை, சிவப்பு மற்றும் நீல மேல் உறைகளின் அனைத்து செங்குத்துகளையும் இடமிருந்து வலமாக மாற்றுகிறது. மிக சமீபத்தில் எதிர்கொள்ளப்பட்ட சிவப்பு மற்றும் நீல புள்ளிகள் லைன் ஸ்வீப்களாக பராமரிக்கப்படுகின்றன. ஒரு புள்ளியை எதிர்கொள்ளும்போது, எதிர் நிறத்தின் கடைசியாக எதிர்கொள்ளப்பட்ட புள்ளியைத் தொடர்ந்து புள்ளி பிரிவின் மேலே அல்லது கீழே உள்ளதா என்பதை வழிமுறை சரிபார்க்கிறது. அது மேலே இருந்தால், அந்த புள்ளி இணைக்கப்பட்ட மேல் உறையில் சேர்க்கப்படும். கடைசியாக சேர்க்கப்பட்ட புள்ளியை விட இது வேறு நிறத்தில் இருந்தால், சிவப்பு மற்றும் நீல உறைகள் கடந்துவிட்டன, எனவே குறுக்குவெட்டு புள்ளியும் இணைக்கப்பட்ட மேல் உறையில் சேர்க்கப்படுகிறது. இந்த வழிமுறையின் விளைவாக ஏற்படும் விளிம்புகள் மற்றும் செங்குத்துகளின் வரிசை புள்ளிகளின் வரிசை மற்றும் வரி-புள்ளி ஒப்பீடுகளின் முடிவுகளை மட்டுமே சார்ந்துள்ளது. எனவே, பின்வரும் சான்றிதழ்களுடன் முடிவை சான்றளிக்க முடியும்ஃ சிவப்பு மற்றும் நீல உறைகளின் செங்குத்துகளை வரிசைப்படுத்த x-சான்றிதழ்கள் () பயன்படுத்தப்படுகின்றன. அவை செங்குத்துகளின் தொகுப்பில் ஒரு இயக்க வரிசைப்படுத்தப்பட்ட பட்டியலுக்கான சான்றிதழ்கள். ஒவ்வொரு புள்ளியும் 2 வரிகளைக் கொண்டிருப்பதால், சான்றிதழில் 2 புள்ளிகள் இருப்பதால், ஒவ்வொரு சான்றிதழிலும் 4 வரிகள் உள்ளன. ஒரு உச்சி ஒரு விளிம்பிற்கு மேலே அல்லது கீழே உள்ளது என்பதை சான்றளிக்க y-சான்றிதழ்கள் () பயன்படுத்தப்படுகின்றன. வழிமுறையின் போது நிகழும் அனைத்து ஒப்பீடுகளுக்கும் சான்றிதழ்கள் தோன்றும். இந்த சான்றிதழ்கள் அனைத்தும் இருக்கும் வரை, இணைக்கும் படிகள் ஒரே மாதிரியாக செயல்படுத்தப்படும், எனவே இதன் விளைவாக வரும் மேல் உறை ஒரே மாதிரியாக இருக்கும். நிலையான மேல் உறை வழிமுறையை சான்றளிக்க இந்த சான்றிதழ்களைப் பயன்படுத்துவதன் மூலம் மேல் உறைகளுக்கான இயக்க தரவு கட்டமைப்பை உருவாக்க முடியும். இருப்பினும், இந்த திட்டம் உள்ளூர் அல்ல, ஏனென்றால் ஒரு வரி மற்ற உறையிலிருந்து பல புள்ளிகள் எதிர்கொள்ளப்படுவதைப் போலவே மேலே அல்லது கீழே இருந்தால் பல ஒய்-சான்றிதழ்களில் பலர் ஈடுபடுவார்கள். எனவே, ஒரு கோட்டின் சாய்வு மற்றொரு கோட்டின் சாய்வை விட அதிகமாகவோ அல்லது குறைவாகவோ உள்ளது என்பதை சான்றளிக்கும் ஒரு எஸ்-சான்றிதழ்களை () அறிமுகப்படுத்துவது அவசியம். அனைத்து புள்ளிகளுக்கும் பின்வரும் சான்றிதழ்களை வைத்திருப்பது ஒரு இணைப்பின் விளைவாக ஏற்படும் விளிம்புகள் மற்றும் செங்குத்துகளின் வரிசையை சான்றளிக்க போதுமானது, ஒரு வரிக்கு O (1) சான்றிதழ்கள் மட்டுமேஃ அதன் வலதுபுறத்தில் மிக நெருக்கமான உச்சியைக் குறிக்கிறது. இந்த சான்றிதழ் அவற்றைப் பின்தொடரும் புள்ளியை விட வேறுபட்ட நிறத்தைக் கொண்ட அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. : அல்லது. இந்த சான்றிதழ் குறுக்கிடும் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. போட்டியாளரின் விளிம்பைக் குறிக்கிறது, மற்ற உறைக்கு மேலே அல்லது கீழே உள்ள விளிம்பைக் குறிக்கிறது. : அல்லது. இந்த சான்றிதழ் குறுக்கிடும் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. :. இந்த சான்றிதழ் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. :. இந்த சான்றிதழ் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. :. இந்த சான்றிதழ் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. :. இந்த சான்றிதழ் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. :. இந்த சான்றிதழ் அனைத்து புள்ளிகளுக்கும் சேமிக்கப்படுகிறது. முதல் சான்றிதழ், சிவப்பு மற்றும் நீல உறைகளில் உள்ள புள்ளிகளின் x-வரிசைப்படுத்தலை சான்றளிக்கிறது. இரண்டாவது மற்றும் மூன்றாவது சான்றிதழ்கள், மற்றும், சிவப்பு மற்றும் நீல உறைகளின் குறுக்குவெட்டுகளை சான்றளிக்கின்றன. மீதமுள்ள 5 சான்றிதழ்கள்,,,, மற்றும் மேல் உறைகளில் இல்லாத விளிம்புகளை அதற்கு மேலே உள்ள விளிம்புகளின் சரிவுகளின் வரிசையில் வைக்கவும். சாய்வு வரிசையின் தொடக்கத்தில் அல்லது முடிவில் இருந்தால், அல்லது இதை சான்றளிக்கவும். இது வரிசையின் நடுவில் இருந்தால், இதைச் சான்றளித்து, விளிம்பின் சாய்வு இடையில் இருக்கும் இரண்டு கோடுகளின் குறுக்குவெட்டு புள்ளி அதற்கு மேலே உள்ளது என்பதை சான்றளிக்கிறது. அனைத்து விளிம்புகளும் இந்த கோட்டிற்கு மேலே உள்ளன என்பதை நிரூபிக்க இந்த ஒன்று அல்லது மூன்று சான்றிதழ்கள் போதுமானது. முந்தைய திட்டத்தைப் போலல்லாமல் அனைத்து வரிசைகளும் நிலையான எண்ணிக்கையிலான சான்றிதழ்களில் மட்டுமே ஈடுபட்டுள்ளன. இந்த சான்றிதழ்களில் ஏதேனும் ஒன்று தோல்வியடையும் போதெல்லாம், இணைக்கப்பட்ட உறை மற்றும் சான்றிதழ்களை ஓ (1) நேரத்தில் புதுப்பிக்கலாம். குவிந்த மேல்புறத்திற்கான இயக்க தரவு அமைப்பு இந்த சான்றிதழ்களைப் பயன்படுத்தி மேல் உறைகளின் தொடர்ச்சியான இணைப்பை சான்றளிக்க கட்டமைக்கப்பட்டுள்ளது. சான்றிதழ்கள் தோல்வியடையும் போதெல்லாம், அவற்றின் இணைப்பு புதுப்பிக்கப்படுகிறது, மேலும் இணைப்பு மாற்றங்களின் விளைவாக ஏற்படும் உறை, இணைப்பின் முடிவைப் பொறுத்து அனைத்து இணைப்புகளிலும் மாற்றங்கள் பரப்பப்படுகின்றன. செயல்திறன் இந்த தரவு அமைப்பு பதிலளிக்கக்கூடிய, உள்ளூர், கச்சிதமான மற்றும் திறமையானது. இது மேல் உறையை சான்றளிக்கப் பயன்படுத்தப்படும் இணைப்புகளின் மடக்கை ஆழம் காரணமாகும். பதில்ஃ ஒரு சான்றிதழ் தோல்வியடையும் போது, அது சான்றளிக்கும் இணைப்பை சரிசெய்ய O (1) எடுக்கும். இதன் விளைவாக வரும் உறை மாறினால், மாற்றப்பட்ட இணைப்பின் முடிவைப் பொறுத்து அனைத்து இணைப்புகளுக்கும் மாற்றம் பரப்பப்பட வேண்டும். O (log n) போன்ற இணைப்புகள் உள்ளன, எனவே புதுப்பிப்பை O (log n) நேர மொத்தத்தில் செய்ய முடியும். உள்ளூர்ஃ ஒவ்வொரு வரியும் அதிக ஓ (லாக் என்) சான்றிதழ்களில் ஈடுபட்டுள்ளது. ஏனென்றால், ஒவ்வொரு இணைப்பிலும் ஒவ்வொரு வரியும் நிலையான எண்ணிக்கையிலான சான்றிதழ்களில் ஈடுபட்டுள்ளன, மேலும் ஒவ்வொரு வரியும் மொத்தமாக O (log n) இணைப்புகளில் உள்ளது. சுருக்கமானதுஃ இந்த தரவு கட்டமைப்பில் பயன்படுத்தப்படும் சான்றிதழ்களின் அதிகபட்ச எண்ணிக்கை O (n log n) ஆகும். ஏனென்றால், ஒவ்வொரு இணைப்பும் இணைக்கப்பட்ட கோடுகளின் எண்ணிக்கையுடன் நேரியல் பல சான்றிதழ்களை உள்ளடக்கியது. n வரிகளின் மேல் உறைக்கு சான்றளிப்பதற்கு n/2 வரிகளின் இரண்டு துணைக்குழுக்களின் இணைக்கப்பட்ட மேல் உறைக்கு சான்றிதழ்கள் மற்றும் உறைகளை இணைப்பதற்கான சான்றிதழ்கள் தேவைப்படுகின்றன. இவ்வாறு n வரிகளின் மேல் உறையை சான்றளிக்கத் தேவையான சான்றிதழ்களின் எண்ணிக்கை, C (n), C (1) = O (1) உடன் C (n) = 2C (n/2) + O (n) மீண்டும் நிகழ்தலை திருப்திப்படுத்துகிறது. வகுத்தல் மற்றும் வெல்வது மறுநிகழ்வுகளுக்கான முதன்மைக் கோட்பாட்டின் படி, C (n) = O (n log n). செயல்திறன்ஃ இயற்கணித அல்லது போலி-இயற்கணித பாதைகளில் இந்த வழிமுறையால் செயலாக்கப்பட்ட அதிகபட்ச நிகழ்வுகளின் எண்ணிக்கை அனைவருக்கும் இருபடிக்கு அருகில் உள்ளது. நேரியல் நகரும் புள்ளிகளின் கன்வெக்ஸ் மேலோட்டங்கள் நேரங்களை மாற்றலாம். எனவே இந்த தரவு அமைப்பு திறமையானது. அதிக பரிமாணங்கள் 2 க்கும் அதிகமான பரிமாணங்களில் நகரும் புள்ளிகளின் குவிந்த மேலோட்டத்தை பராமரிப்பதற்கான திறமையான இயக்க தரவு கட்டமைப்பைக் கண்டறிவது ஒரு திறந்த சிக்கலாகும். தொடர்புடைய சிக்கல்கள் பின்வரும் தொடர்புடைய சிக்கல்களைத் தீர்க்க கைனெட்டிக் குவிந்த ஹல் பயன்படுத்தப்படலாம்ஃ கைனெட்டிக் விட்டம் கைனெட்டிக் அகலம் கைனெட்டிக் குறைந்தபட்ச பெட்டி கைனெட்டிக் மிகச்சிறிய அடைக்கப்பட்ட வட்டு குறிப்புகள் கைனெட்டிக் தரவு கட்டமைப்புகள் கன்வெக்ஸ் ஹல் வழிமுறைகள்