Klee's measure problem
कम्प्यूटेशनल ज्यामिति में, क्ली की माप समस्या यह निर्धारित करने की समस्या है कि (बहुआयामी) आयताकार श्रेणियों के संयोजन के माप की गणना कितनी कुशलता से की जा सकती है। यहाँ, एक डी-आयामी आयताकार सीमा को वास्तविक संख्याओं के डी अंतराल के एक कार्टेशियन उत्पाद के रूप में परिभाषित किया गया है, जो आरडी का एक उपसमुच्चय है। इस समस्या का नाम विक्टर क्ली के नाम पर रखा गया है, जिन्होंने अंतरालों के संयोजन की लंबाई की गणना के लिए एक एल्गोरिथ्म दिया (मामला डी = 1) जिसे बाद में कम्प्यूटेशनल जटिलता सिद्धांत के अर्थ में इष्टतम रूप से कुशल दिखाया गया था। 2-आयामी आयताकार श्रेणियों के संघ के क्षेत्र की गणना करने की कम्प्यूटेशनल जटिलता अब भी ज्ञात है, लेकिन मामला d ≤ 3 एक खुली समस्या बनी हुई है। इतिहास और एल्गोरिदम 1977 में, विक्टर क्ली ने निम्नलिखित समस्या पर विचार कियाः वास्तविक रेखा में n अंतरालों के संग्रह को देखते हुए, उनके संघ की लंबाई की गणना करें। इसके बाद उन्होंने कम्प्यूटेशनल जटिलता (या "रनिंग टाइम") के साथ इस समस्या को हल करने के लिए एक एल्गोरिथ्म प्रस्तुत किया-इस कथन के अर्थ के लिए बिग ओ संकेतन देखें। अंतरालों को क्रमबद्ध करने पर आधारित इस एल्गोरिथ्म को बाद में माइकल फ्रेडमैन और ब्रूस वीड (1978) द्वारा इष्टतम दिखाया गया था। बाद में 1977 में, जॉन बेंटले ने इस समस्या के दो-आयामी अनुरूप पर विचार कियाः n आयतों के संग्रह को देखते हुए, उनके संघ के क्षेत्र का पता लगाएं। उन्होंने एक जटिलता एल्गोरिथ्म भी प्राप्त किया, जिसे अब बेंटले के एल्गोरिथ्म के रूप में जाना जाता है, जो समस्या को एन 1-आयामी समस्याओं तक कम करने पर आधारित हैः यह पूरे क्षेत्र में एक ऊर्ध्वाधर रेखा को साफ करके किया जाता है। इस विधि का उपयोग करके, संघ के क्षेत्र की गणना स्पष्ट रूप से संघ का निर्माण किए बिना की जा सकती है। बेंटले के एल्गोरिथ्म को अब इष्टतम (द्वि-आयामी मामले में) के रूप में भी जाना जाता है, और इसका उपयोग अन्य क्षेत्रों के साथ-साथ कंप्यूटर ग्राफिक्स में भी किया जाता है। ये दो समस्याएं एक अधिक सामान्य प्रश्न के 1-और 2-आयामी मामले हैंः एन डी-आयामी आयताकार श्रेणियों के संग्रह को देखते हुए, उनके संघ के माप की गणना करें। यह सामान्य समस्या क्ली की माप समस्या है। जब डी-आयामी मामले में सामान्यीकृत किया जाता है, तो बेंटले के एल्गोरिथ्म का चलने का समय होता है। यह इष्टतम नहीं है, क्योंकि यह केवल डी-आयामी समस्या को एन (डी-1)-आयामी समस्याओं में विघटित करता है, और उन उप-समस्याओं को आगे विघटित नहीं करता है। 1981 में, जान वैन लीउवेन और डेरेक वुड ने डायनेमिक क्वाडट्री का उपयोग करके इस एल्गोरिथ्म के चलने के समय में सुधार किया। 1988 में, मार्क ओवरमार्स और ची याप ने डी ≤ 3 के लिए एक एल्गोरिथ्म का प्रस्ताव रखा। उनका एल्गोरिथ्म समस्या को 2-आयामी घटकों में विघटित करने और उन घटकों को कुशलता से एकत्रित करने के लिए एक केडी-ट्री के समान एक विशेष डेटा संरचना का उपयोग करता है; 2-आयामी समस्याओं को स्वयं एक ट्रेलिस संरचना का उपयोग करके कुशलता से हल किया जाता है। हालांकि बेंटले के एल्गोरिदम की तुलना में एसिम्प्टोटिक रूप से तेज, इसकी डेटा संरचनाएं काफी अधिक स्थान का उपयोग करती हैं, इसलिए इसका उपयोग केवल उन समस्याओं में किया जाता है जहां n या d बड़ा होता है। 1998 में, बोग्डन क्लेबस ने सामान्य विशेष मामलों के लिए समान एसिम्प्टोटिक रनिंग टाइम के साथ एक सरल एल्गोरिथ्म का प्रस्ताव रखा जहां डी 3 या 4 है। 2013 में, टिमोथी एम. चैन ने एक सरल एल्गोरिथ्म विकसित किया जो गतिशील डेटा संरचनाओं की आवश्यकता से बचाता है और लॉगरिदमिक कारक को समाप्त करता है, जिससे डी ≤ 3 के लिए सबसे अच्छा ज्ञात चलने का समय कम हो जाता है। ज्ञात सीमाएँ किसी भी डी के लिए एकमात्र ज्ञात निचली सीमा है, और इस चलने वाले समय के साथ इष्टतम एल्गोरिदम डी = 1 और डी = 2 के लिए जाने जाते हैं। चैन एल्गोरिथ्म डी ≤ 3 के लिए एक ऊपरी सीमा प्रदान करता है, इसलिए डी ≤ 3 के लिए, यह एक खुला सवाल बना हुआ है कि क्या तेज एल्गोरिथ्म संभव हैं, या वैकल्पिक रूप से क्या सख्त निचली सीमाएं साबित की जा सकती हैं। विशेष रूप से, यह खुला रहता है कि क्या एल्गोरिथ्म का चलने का समय डी पर निर्भर होना चाहिए। इसके अलावा, यह सवाल खुला रहता है कि क्या ऐसे तेज़ एल्गोरिदम हैं जो विशेष मामलों से निपट सकते हैं (उदाहरण के लिए, जब इनपुट निर्देशांक एक सीमित सीमा के भीतर पूर्णांक होते हैं)। 1डी क्ली की माप समस्या (अंतरालों का संयोजन) को हल किया जा सकता है जहां पी सभी अंतरालों को छुरा घोंपने के लिए आवश्यक छेद बिंदुओं की संख्या को दर्शाता है (एक सामान्य बिंदु द्वारा छेद किए गए अंतरालों के संयोजन की गणना चरम सीमा की गणना करके रैखिक समय में की जा सकती है)। पैरामीटर पी एक अनुकूली पैरामीटर है जो इनपुट विन्यास पर निर्भर करता है, और भेदी एल्गोरिथ्म क्ली की माप समस्या के लिए एक अनुकूली एल्गोरिथ्म देता है। कन्वेक्स आयतन सन्निकटन भी देखें, जो उत्तल निकायों के लिए एक कुशल एल्गोरिथ्म संदर्भ और आगे महत्वपूर्ण पत्रों को पढ़ना है। .. .. .. .. .. .. माध्यमिक साहित्य फ्रेंको पी. प्रिपेराटा और माइकल आई. शामोस (1985)। कम्प्यूटेशनल ज्यामिति (स्प्रिंगर-वेरलैग, बर्लिन)। प्रोफेसर जेफ एरिकसन की कम्प्यूटेशनल ज्यामिति में खुली समस्याओं की सूची से क्ली की माप समस्या। (8 नवंबर, 2005 तक पहुँचा, जब अंतिम अद्यतन 31 जुलाई, 1998 था।) संदर्भ कम्प्यूटेशनल ज्यामिति मापन सिद्धांत गणितीय समस्याएं