رسم بياني للجوار النسبي

في الهندسة الحسابية ، يُعد مخطط الجوار النسبي ( RNG ) مخططًا غير موجه يُعرَّف على مجموعة من النقاط في المستوى الإقليدي عن طريق ربط نقطتين.${\displaystyle p}$و${\displaystyle q}$بواسطة حافة عندما لا توجد نقطة ثالثة${\displaystyle r}$هذا أقرب إلى كليهما${\displaystyle p}$و${\displaystyle q}$أكثر مما هم عليه بالنسبة لبعضهم البعض. اقترح غودفريد توسان هذا الرسم البياني في عام 1980 كوسيلة لتحديد بنية من مجموعة من النقاط تتوافق مع التصورات البشرية لشكل المجموعة. ^{[ 1 ] [ 2 ]}

أوضح سوبويت (1983) كيفية إنشاء الرسم البياني للجوار النسبي لـ${\displaystyle n}$النقاط في المستوى بكفاءة${\displaystyle O(n\log n)}$الوقت. ^{[ 3 ]} يمكن حسابه في${\displaystyle O(n)}$الوقت المتوقع لمجموعة عشوائية من النقاط موزعة بانتظام في المربع الواحدي . ^{[ 4 ]} يمكن حساب الرسم البياني للجوار النسبي في وقت خطي من خلال تثليث ديلاوناي لمجموعة النقاط. ^{[ 5 ] [ 6 ]}

نظرًا لأن الرسم البياني للجوار النسبي يُعرَّف فقط بدلالة المسافات بين النقاط، فإنه يُمكن تعريفه لمجموعات النقاط في أي بُعد، ^{[ 1 ] [ 7 ] [ 8 ]} وللمقاييس غير الإقليدية. ^{[ 1 ] [ 5 ] [ 9 ] [ 10 ]} يُمكن حساب الرسم البياني للجوار النسبي، لمجموعات النقاط ذات الأبعاد الأعلى، في وقت${\displaystyle O(n^{2})}$.

يُعدّ مخطط الجوار النسبي مثالاً على هيكل بيتا قائم على العدسة . وهو مخطط فرعي من تثليث ديلاوناي . وبدورها، تُعدّ شجرة الامتداد الأدنى الإقليدية مخططًا فرعيًا منه، ومن ثمّ يتبين أنه مخطط متصل .

تم اقتراح مخطط أوركهارت ، وهو المخطط الناتج عن إزالة أطول ضلع من كل مثلث في تثليث ديلاوناي، في الأصل كطريقة سريعة لحساب مخطط الجوار النسبي. ^{[ 11 ]} على الرغم من أن مخطط أوركهارت قد يختلف أحيانًا عن مخطط الجوار النسبي ^{[ 12 ]،} إلا أنه يمكن استخدامه كتقريب له. ^{[ 13 ]}