हॉसडॉर्फ दूरी

गणित में हॉसडॉर्फ दूरी या हॉसडॉर्फ मीट्रिक को पोम्पेउ-हॉउसडॉर्फ दूरी भी कहा जाता है यह एक मीट्रिक स्थान के दो उपसमुच्चयों की एक दूसरे से दूरी मापता हैं। यह गैर-रिक्त समुच्चय के समुच्चय को परिवर्तित कर देता है, मीट्रिक स्पेस के गैर-रिक्त सघन स्थान उपसमुच्चयअपने आप को मीट्रिक स्थान में परिवर्तित कर देता है। इसका नाम फेलिक्स हॉसडॉर्फ और डेमेट्रियस पॉम्पी के नाम पर रखा गया है।

अनौपचारिक रूप से हॉसडॉर्फ दूरी में दो समुच्चय निकट होते हैं यदि समुच्चय के प्रत्येक बिंदु दूसरे समुच्चय के किसी बिंदु के निकट है। हॉसडॉर्फ दूरी वह सबसे लंबी दूरी है जहाँ आपको विपक्षी द्वारा जाने के लिए प्रेरित किया जाता है जो दो समुच्चयों में से एक में बिंदु का चुनाव करता है जहां से आपको दूसरे समुच्चय की ओर जाना चाहिये। दूसरे शब्दों में यह दूरी समुच्चय में एक बिंदु से दूसरे समुच्चय में निकटतम बिंदु तक की सभी दूरियों में से सबसे बड़ी है।

इस दूरी को हॉसडॉर्फ ने पहली बार 1914 में प्रथम बार प्रकाशित अपनी पुस्तक ग्रंडजुगे डेर मेंजेनलेह्रे में प्रस्तुत किया था जबकि मौरिस रेने फ्रेचेट के डॉक्टरेट थीसिस में एक बहुत निकटतम सम्बन्धी $[0,1]\to \mathbb {R} ^{3}$ सम्मुख आया था।

परिभाषा

ग्रीन कर्व X और ब्लू कर्व Y के बीच हॉसडॉर्फ दूरी की गणना के घटक।

माना कि X और Y मीट्रिक स्पेस के दो गैर-रिक्त उपसमुच्चय $(M,d)$ हैं, हम उनकी हॉसडॉर्फ दूरी को $d_{\mathrm {H} }(X,Y)$ द्वारा

परिभाषित करते हैं,

$d_{\mathrm {H} }(X,Y)=\max \left\{\,\sup _{x\in X}d(x,Y),\,\sup _{y\in Y}d(X,y)\,\right\},\!$

जहाँ sup सर्वोच्चता का प्रतिनिधित्व करता है, इन्फ़ीमुम का प्रतिनिधित्व करता है और जहाँ $d(a,B)=\inf _{b\in B}d(a,b)$ एक बिंदु $a\in X$ उपसमुच्चय की $B\subseteq X$ से दूरी की गणना करता है।

समान रूप से,

$d_{H}(X,Y)=\inf\{\varepsilon \geq 0\,;\ X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq X_{\varepsilon }\},\quad$

जहाँ

$X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\,;\ d(z,x)\leq \varepsilon \},$

अर्थात् भीतर सभी बिंदुओं का समुच्चय $\varepsilon$ समुच्चय $X$ का (कभी-कभी $X$ का $\varepsilon$- मोटा होना या त्रिज्या $\varepsilon$ की सामान्यीकृत गेंद (गणित) $X$ के आस-पास कहा जाता है).

समान रूप से,

$d_{H}(X,Y)=\sup _{w\in M}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|=\sup _{w\in X\cup Y}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|,$

वह है $d_{\mathrm {H} }(X,Y)=\sup _{w\in M}|d(w,X)-d(w,Y)|$

जहाँ समुच्चय $X$ की बिंदु $w$ से दूरी $d(w,X)$ है।

टिप्पणी

यह स्वेच्छाचारी उपसमुच्चय $X,Y\subset M$ जो कि $d_{\mathrm {H} }(X,Y)=\varepsilon$ हेतु सत्य नहीं है तात्पर्य

$X\subseteq Y_{\varepsilon }\ {\mbox{and}}\ Y\subseteq X_{\varepsilon }.$

उदाहरण के लिए वास्तविक संख्याओं के मीट्रिक स्थान $\mathbb {R}$ पर विचार करें सामान्य मीट्रिक के साथ $d$ निरपेक्ष मूल्य से प्रेरित,

$d(x,y):=|y-x|,\quad x,y\in \mathbb {R} .$

लिया,

$X:=(0,1]\quad {\mbox{and}}\quad Y:=[-1,0).$

तब $d_{\mathrm {H} }(X,Y)=1\$जबकि $X\nsubseteq Y_{1}$ क्योंकि $Y_{1}=[-2,1)\$, परन्तु $1\in X$

परन्तु यह सत्य है कि $X\subseteq {\overline {Y_{\varepsilon }}}$ और $Y\subseteq {\overline {X_{\varepsilon }}}$ विशेष रूप से सत्य है यदि $X,Y$ बंद हो जाते हैं।

गुण

• सामान्य रूप में $d_{\mathrm {H} }(X,Y)$ अनंत हो सकता है। यदि X और Y दोनों समुच्चय हैं तो $d_{\mathrm {H} }(X,Y)$ परिमित होने की गारंटी है।
• अगर $d_{\mathrm {H} }(X,Y)=0$ और केवल अगर X और Y का एक ही प्रकार बंद होना है।
• M के प्रत्येक बिंदु x के लिए और किसी भी गैर-रिक्त समुच्चय Y, M के Z के लिए: d(x,Y) ≤ d(x,Z) + d_H(वाई, जेड), जहां D (X, Y) बिंदु X और समुच्चय Y में निकटतम बिंदु के मध्य की दूरी है।
• |व्यास(Y)-व्यास(X)| ≤ 2 d_H(X, Y)।
• यदि प्रतिच्छेदन X ∩ Y का आंतरिक भाग रिक्त नहीं है तो स्थिरांक r > 0 उपस्थित होता है जैसे कि प्रत्येक समुच्चय X' जिसकी हॉसडॉर्फ की दूरी X से कम है Y को भी प्रतिच्छेद करता है।
• M के सभी उपसमुच्चयों के समुच्चय पर, d_H एक विस्तारित स्यूडोमेट्रिक स्पेस देता है।
• M, D_H के सभी गैर-रिक्त सघन उपसमुच्चय के समुच्चय F(M) पर एक पैमाना है।
  • यदि M पूर्ण मीट्रिक स्थान है, तो F(M) भी ​​है।
  • यदि M सघन है तो F(M) भी है।
  • F(M) का टोपोलॉजिकल स्थान केवल M के टोपोलॉजी पर निर्भर करता है मेट्रिक d पर नहीं।

प्रेरणा

हॉसडॉर्फ दूरी की परिभाषा दूरी समारोह के प्राकृतिक विस्तार की श्रृंखला $d(x,y)$ से प्राप्त की जा सकती है जहाँ अंतर्निहित मीट्रिक स्थान M में इस प्रकार है:

• M के किसी भी बिंदु x और M के किसी भी गैर-रिक्त समुच्चय Y के मध्य दूरी फलन को परिभाषित करें:

$d(x,Y)=\inf\{d(x,y)\mid y\in Y\}.\$

उदाहरण के लिए, d (1, {3,6}) = 2 और d (7, {3,6}) = 1।

• M के किसी भी दो गैर-रिक्त समुच्चय X और Y के मध्य (सममित-आवश्यक-नहीं) दूरी फलन परिभाषित करें:

$d(X,Y)=\sup\{d(x,Y)\mid x\in X\}.\$

उदाहरण के लिए ${\textstyle d(\{1,7\},\{3,6\})=\sup\{d(1,\{3,6\}),d(7,\{3,6\})\}=\sup\{d(1,3),d(7,6)\}=2.}$

• यदि X और Y सघन हैं तो d (X, Y) परिमित होगा; d (X, X) = 0; और d त्रिभुज असमानता गुणों को M में दूरी फलन से प्राप्त करता है। जैसा कि स्थित है कि d (X, Y) मीट्रिक नहीं है क्योंकि d (X, Y) सदैव सममित नहीं है और d(X,Y) = 0 का अर्थ X = Y (इसका अर्थ यह है $X\subseteq Y$) नहीं है उदाहरण के लिए d({1,3,6,7}, {3,6}) = 2 किन्तु d({3,6}, {1,3,6,7}) = 0 जबकि हम हॉसडॉर्फ दूरी को परिभाषित करके मीट्रिक बना सकते हैं:

$d_{\mathrm {H} }(X,Y)=\max\{d(X,Y),d(Y,X)\}\,.$

अनुप्रयोग

कंप्यूटर दृष्टि में हॉसडॉर्फ दूरी का उपयोग एकपक्षीय लक्ष्य छवि में दिए गए टेम्पलेट को खोजने के लिए किया जा सकता है। नमूना और छवि को अधिकतर सीमा सूचकांक के माध्यम से पूर्व-प्रक्रमक किया जाता है जिससे द्विआधारी छवि मिलती है। टेम्पलेट की बाइनरी छवि में प्रत्येक 1 (सक्रिय) बिंदु को समुच्चय में एक बिंदु टेम्पलेट के आकार के रूप में माना जाता है। इसी प्रकार बाइनरी लक्ष्य छवि के क्षेत्र को बिंदुओं के समूह के रूप में माना जाता है। एल्गोरिथ्म तब टेम्पलेट और लक्ष्य छवि के कुछ क्षेत्र के मध्य हॉसडॉर्फ की दूरी को कम करने का प्रयत्न करता है। लक्ष्य छवि में टेम्पलेट के लिए न्यूनतम हॉसडॉर्फ दूरी वाले क्षेत्र को लक्ष्य में टेम्पलेट को ज्ञात करने के लिए सबसे अच्छा उम्मीदवार माना जा सकता है।

कंप्यूटर चित्रलेख में हॉसडॉर्फ दूरी का उपयोग एक ही 3d ऑब्जेक्ट के दो अलग-अलग प्रतिनिधित्वों के मध्य अंतर को मापने के लिए किया जाता है विशेष रूप से जटिल 3D प्रारूप के कुशल प्रदर्शन के लिए विस्तार का स्तर (कंप्यूटर ग्राफिक्स) उत्पन्न करते समय।

अगर $X$ पृथ्वी की सतह है, और $Y$ पृथ्वी की भूमि-सतह है तो निमो बिंदु खोजने पर हम देखते हैं $d_{H}(X,Y)$ लगभग 2,704.8 किमी है।

अगम्यता का महासागरीय ध्रुव

संबंधित अवधारणाएं

आइसोमेट्री तक हॉसडॉर्फ दूरी द्वारा दो आकृतियों की असमानता के लिए एक उपाय दिया गया है जिसे D_H द्वारा निरूपित किया गया है अर्थात् X और Y को मीट्रिक स्पेस M (सामान्य रूप से यूक्लिडियन अंतरिक्ष) में दो कॉम्पैक्ट आंकड़े होने दें तब D_H(X, Y) का न्यूनतम d_H(I(X),Y) है जहां मीट्रिक स्पेस M के सभी आइसोमेट्री I के साथ आते हैं। यह दूरी मापती है कि आकार X और Y सममितीय होने से कितनी दूर हैं।

ग्रोमोव-हॉसडॉर्फ अभिसरण एक संबंधित विचार है: हम दो मीट्रिक रिक्त स्थान M और N की दूरी को कम से कम $d_{\mathrm {H} }(I(M),J(N))$ लेते हुए कुछ सामान्य मीट्रिक स्थान L में सभी आइसोमेट्रिक एम्बेडिंग के साथ $I\colon M\to L$ और $J\colon N\to L$ मापते हैं

यह भी देखें

• विज्समैन अभिसरण
• कुराटोव्स्की अभिसरण
• अर्ध निरंतरता
• फ्रेचेट दूरी

बाहरी संबंध

• Hausdorff distance between convex polygons.
• Using MeshLab to measure difference between two surfaces A short tutorial on how to compute and visualize the Hausdorff distance between two triangulated 3D surfaces using the open source tool MeshLab.
• MATLAB code for Hausdorff distance: [1]