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

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

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

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

प्रेरणा

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

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

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

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

• एम के किसी भी दो गैर-खाली सेट एक्स और वाई के बीच एक (जरूरी नहीं-सममित) दूरी फ़ंक्शन परिभाषित करें:

$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.}$

• यदि एक्स और वाई कॉम्पैक्ट हैं तो डी (एक्स, वाई) परिमित होगा; डी (एक्स, एक्स) = 0; और डी त्रिभुज असमानता संपत्ति को एम में दूरी समारोह से प्राप्त करता है। जैसा कि यह खड़ा है, डी (एक्स, वाई) एक मीट्रिक नहीं है क्योंकि डी (एक्स, वाई) हमेशा सममित नहीं है, और 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 (सक्रिय) बिंदु को सेट में एक बिंदु के रूप में माना जाता है, टेम्पलेट का आकार। इसी तरह, बाइनरी लक्ष्य छवि के क्षेत्र को बिंदुओं के समूह के रूप में माना जाता है। एल्गोरिथ्म तब टेम्पलेट और लक्ष्य छवि के कुछ क्षेत्र के बीच हॉसडॉर्फ की दूरी को कम करने की कोशिश करता है। लक्ष्य छवि में टेम्पलेट के लिए न्यूनतम हॉसडॉर्फ दूरी वाले क्षेत्र को लक्ष्य में टेम्पलेट का पता लगाने के लिए सबसे अच्छा उम्मीदवार माना जा सकता है। कंप्यूटर चित्रलेख में हॉसडॉर्फ दूरी का उपयोग एक ही 3डी ऑब्जेक्ट के दो अलग-अलग प्रतिनिधित्वों के बीच अंतर को मापने के लिए किया जाता है विशेष रूप से जटिल 3डी मॉडल के कुशल प्रदर्शन के लिए विस्तार का स्तर (कंप्यूटर ग्राफिक्स) उत्पन्न करते समय।

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

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

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

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

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