الشجرة الممتدة الدنيا الإقليدية

الشجرة الممتدة الدنيا الإقليدية لمجموعة محدودة من النقاط في المستوى الإقليدي أو الفضاء الإقليدي ذي الأبعاد الأعلى ، تربط هذه النقاط بنظام من القطع المستقيمة ، حيث تمثل النقاط نهاياتها، مما يقلل الطول الإجمالي لهذه القطع. في هذه الشجرة، يمكن لأي نقطتين الوصول إلى بعضهما البعض عبر مسار يمر بهذه القطع المستقيمة. ويمكن إيجادها كشجرة ممتدة دنيا لرسم بياني كامل ، حيث تمثل النقاط رؤوسه، والمسافات الإقليدية بين النقاط تمثل أوزان حوافه.

تتقاطع حواف الشجرة الممتدة الدنيا بزوايا لا تقل عن 60 درجة، ولا تزيد عن ست زوايا لكل رأس. في الأبعاد الأعلى، يكون عدد الحواف لكل رأس محدودًا بعدد الكرات المماسية المتلامسة . الطول الإجمالي للحواف، بالنسبة للنقاط في مربع الوحدة ، لا يزيد عن الجذر التربيعي لعدد النقاط. تقع كل حافة في منطقة فارغة من المستوى، ويمكن استخدام هذه المناطق لإثبات أن الشجرة الممتدة الدنيا الإقليدية هي رسم بياني فرعي من رسوم بيانية هندسية أخرى ، بما في ذلك رسم بياني الجوار النسبي وتثليث ديلاوناي . من خلال إنشاء تثليث ديلاوناي ثم تطبيق خوارزمية الشجرة الممتدة الدنيا للرسم البياني، نحصل على الشجرة الممتدة الدنيا لـ $n$ يمكن إيجاد النقاط المستوية المعطاة في الوقت $O(n\log n)$ كما هو مُعبَّر عنه برمز Big O. يُعدّ هذا الأمثل في بعض نماذج الحوسبة، على الرغم من وجود خوارزميات عشوائية أسرع للنقاط ذات الإحداثيات الصحيحة. أما بالنسبة للنقاط في الأبعاد الأعلى، فلا يزال إيجاد خوارزمية مثلى مسألة مفتوحة .

التعريف والمشاكل ذات الصلة

شجرة الامتداد الأدنى الإقليدية، لمجموعة من $n$ تُعرَّف الشبكة الإقليدية، التي تُمثل نقاطًا في المستوى الإقليدي أو الفضاء الإقليدي ، بأنها نظام من القطع المستقيمة ، حيث تكون النقاط المُعطاة هي نهاياتها فقط، ويشمل اتحادها جميع النقاط في مجموعة متصلة ، وتتميز بأقصر طول إجمالي ممكن لأي نظام من هذا النوع. لا يمكن أن تحتوي هذه الشبكة على حلقة مضلعة من القطع المستقيمة ؛ فإذا وُجدت، يُمكن تقصير الشبكة بإزالة أحد أضلاع المضلع. لذلك، تُشكل الشبكة ذات الطول الأدنى شجرة . تقود هذه الملاحظة إلى تعريف مُكافئ مفاده أن الشجرة الإقليدية الممتدة الدنيا هي شجرة من القطع المستقيمة بين أزواج النقاط المُعطاة، ذات أقصر طول إجمالي. ^{[ 1 ]} يُمكن أيضًا وصف الشجرة نفسها بأنها شجرة ممتدة دنيا لرسم بياني كامل مُثقَّل ، حيث تكون النقاط المُعطاة هي رؤوسها والمسافات بين النقاط هي أوزان أضلاعها. ^{[ 2 ]} قد يكون للنقاط نفسها أكثر من شجرة ممتدة دنيا. على سبيل المثال، بالنسبة لرؤوس مضلع منتظم ، تُنتج إزالة أي ضلع من المضلع شجرة ممتدة دنيا. ^{[ 3 ]}

تُختصر عادةً في المنشورات المتعلقة بشجرة الامتداد الأدنى الإقليدية إلى "EMST". ^{[ 4 ]}^{[ 5 ]} وقد تُسمى أيضًا "أشجار الامتداد الأدنى الهندسية"، ^{[ 6 ]}^{[ 7 ]} ولكن هذا المصطلح يُستخدم بشكل أعم للفضاءات الهندسية ذات المسافات غير الإقليدية، مثل فضاءات $Lp$ $.$ [ ^{8 ] وعندما} يكون سياق مجموعات النقاط الإقليدية واضحًا، يُمكن تسميتها ببساطة "أشجار الامتداد الأدنى". ^{[ 9 ]}^{[ 10 ]}^{[ 11 ]}

ترتبط العديد من الشبكات الهندسية القياسية الأخرى ارتباطًا وثيقًا بشجرة الامتداد الأدنى الإقليدية:

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

ملكيات

الزوايا ودرجات الرأس

اثنتا عشرة كرة وحدة، جميعها مماسية لكرة وحدة مركزية. الشجرة الممتدة الدنيا لنقاطها المركزية الثلاث عشرة لها درجة 12 عند النقطة المركزية.

عندما يلتقي ضلعان من شجرة الامتداد الأدنى الإقليدية عند رأس، يجب أن يشكلا زاوية 60° أو أكثر، ولا يتساوى الضلعان إلا إذا شكلا ضلعين من مثلث متساوي الأضلاع . والسبب في ذلك هو أنه في حالة وجود ضلعين يشكلان زاوية أقل حدة، يمكن استبدال أحدهما بالضلع الثالث الأقصر من المثلث الذي يشكلانه، مما ينتج عنه شجرة ذات طول إجمالي أصغر. ^{[ 14 ]} في المقابل، تتميز مسألة شجرة شتاينر بحد زاوية أقوى: فشجرة شتاينر المثلى تحتوي على جميع الزوايا التي لا تقل عن 120°. ^{[ 12 ]}

يظهر حد الزاوية نفسه البالغ 60 درجة في مسألة عدد التلامس ، وهي إيجاد أكبر عدد من الكرات الوحدوية في الفضاء الإقليدي التي يمكن أن تكون مماسية لكرة وحدوية مركزية دون أن تتقاطع أي كرتين (بعد نقطة تماس). تمتلك النقاط المركزية لهذه الكرات شجرة ممتدة دنيا على شكل نجمة ، حيث تكون النقطة المركزية مجاورة لجميع النقاط الأخرى. وبالعكس، لأي رأس $v$ لأي شجرة امتداد دنيا، يمكن إنشاء كرات وحدة غير متداخلة متمركزة عند $v$ وعند النقاط التي تبعد وحدتين على طول كل من حوافها، مع تماس لكل جار من $v$ لذلك، في $n$ في الفضاء ذي الأبعاد n، تساوي الدرجة القصوى الممكنة لرأس (عدد حواف الشجرة الممتدة المتصلة به) عدد الكرات المتلامسة في $n$ الأبعاد. ^{[ 15 ]} الأشجار الممتدة الدنيا المستوية لها درجة لا تتجاوز ستة، وعندما تكون درجة الشجرة ستة، توجد دائمًا شجرة ممتدة دنيا أخرى بدرجة قصوى خمسة. ^{[ 7 ]} الأشجار الممتدة الدنيا ثلاثية الأبعاد لها درجة لا تتجاوز اثني عشر. ^{[ 15 ]} الأبعاد الأعلى الوحيدة التي تُعرف فيها القيمة الدقيقة لعدد التقبيل هي أربعة وثمانية و24 بُعدًا. ^{[ 16 ]}

بالنسبة للنقاط المولدة عشوائيًا من توزيع مستمر معين، فإن الشجرة الممتدة الدنيا تكون فريدة بشكل شبه مؤكد . يتقارب عدد رؤوس أي درجة معينة، عند وجود عدد كبير من الرؤوس، إلى قيمة ثابتة مضروبة في ذلك العدد من الرؤوس. تعتمد قيم هذه الثوابت على الدرجة والتوزيع. مع ذلك، حتى في الحالات البسيطة - مثل عدد الأوراق للنقاط الموزعة بانتظام في مربع وحدة - فإن قيمها الدقيقة غير معروفة. ^{[ 17 ]}

المناطق الفارغة

لأي شيء $uv$ في أي شجرة امتداد دنيا إقليدية، العدسة (أو الحويصلة السمكية ) المتكونة من تقاطع الدائرتين مع $uv$ لأن أنصاف أقطارها لا يمكن أن يكون لها أي رأس آخر معطى $w$ في داخلها. بعبارة أخرى، إذا كان لأي شجرة حافة $uv$ تحتوي عدستها على نقطة ثالثة $w$ إذن، فهي ليست ذات طول أدنى. لأنه، بحسب هندسة الدائرتين، $w$ سيكون أقرب إلى كليهما $u$ و $v$ أكثر مما هم عليه بالنسبة لبعضهم البعض. إذا كان الحافة $uv$ أُزيلت من الشجرة، $w$ سيظل متصلاً بأحد $u$ و $v$ ولكن ليس الآخر. استبدال الحافة التي تمت إزالتها $uv$ بواسطة $uw$ أو $vw$ (أي من هذين الحافتين يعيد الاتصال) $w$ ^[¹²^] إن ربطها بالرأس الذي انفصلت عنه سينتج شجرة أقصر.

لأي شيء $uv$ لأي شجرة امتداد دنيا إقليدية، المعين ذو الزوايا 60 درجة و120 درجة، الذي $uv$ باعتباره قطره الطويل، فهو منفصل عن المعينات المتكونة بشكل مماثل من جميع الحواف الأخرى. لا يمكن أن يكون لحافتين تشتركان في نقطة نهاية معينات متداخلة، لأن ذلك سيؤدي إلى زاوية حافة أكبر من 60 درجة، ولا يمكن أن يكون لحافتين منفصلتين معينات متداخلة؛ إذا حدث ذلك، يمكن استبدال الحافة الأطول بحافة أقصر من بين الرؤوس الأربعة نفسها. ^{[ 12 ]}

سوبرغرافز

تتضمن بعض الرسوم البيانية الهندسية تعريفات تشمل مناطق فارغة في مجموعات النقاط، ومن ثمّ تستنتج أنها تحتوي على كل حافة يمكن أن تكون جزءًا من شجرة امتداد إقليدية دنيا. وتشمل هذه:

الرسم البياني للجوار النسبي ، والذي يحتوي على حافة بين أي زوج من النقاط كلما كانت العدسة التي يحددونها فارغة.
الرسم البياني لغابرييل ، الذي يحتوي على حافة بين أي زوج من النقاط عندما تكون الدائرة التي يكون الزوج قطرها فارغة.
التثليث ديلاوناي ، الذي يحتوي على حافة بين أي زوج من النقاط كلما وُجدت دائرة فارغة تحتوي على الزوج كوتر.
يُشكّل مخطط أوركهارت من تثليث ديلاوناي عن طريق إزالة أطول ضلع في كل مثلث. بالنسبة لكل ضلع متبقٍ، لا يمكن أن تقع رؤوس مثلثات ديلاوناي التي تستخدم هذا الضلع داخل الهلال الفارغ لمخطط الجوار النسبي.

نظرًا لأن معايير المنطقة الفارغة لهذه الرسوم البيانية تضعف تدريجيًا، فإنها تُشكّل سلسلة مُرتبة من الرسوم البيانية الفرعية. أي، باستخدام الرمز "⊆" للدلالة على علاقة المجموعة الفرعية بين حوافها، فإن هذه الرسوم البيانية لها العلاقات التالية:

شجرة الامتداد الأدنى الإقليدية ⊆ رسم بياني للجوار النسبي ⊆ رسم بياني أوركهارت ⊆ رسم بياني غابرييل ⊆ تثليث ديلاوناي. ^{[ 18 ]}^{[ 19 ]}

يُعدّ مخطط ياو مثالًا آخر على المخططات التي تضمن احتواءها على الشجرة الممتدة الدنيا ، ويُحدد هذا المخطط لنقاط في المستوى بتقسيم المستوى المحيط بكل نقطة إلى ستة قطاعات بزاوية 60 درجة، وربط كل نقطة بأقرب جار لها في كل قطاع. يحتوي المخطط الناتج على مخطط الجوار النسبي، لأن أي رأسين لهما عدسة فارغة يجب أن يكونا أقرب جارين لبعضهما البعض في قطاعاتهما. وكما هو الحال مع العديد من المخططات الهندسية الأخرى المذكورة أعلاه، يمكن تعميم هذا التعريف إلى أبعاد أعلى، وعلى عكس تثليث ديلاوناي، فإن تعميماته تتضمن دائمًا عددًا خطيًا من الحواف. ^{[ 20 ]}^{[ 21 ]}

الطول الإجمالي

ل $n$ بالنسبة للنقاط الموجودة في المربع الواحدي (أو أي شكل ثابت آخر)، فإن الطول الإجمالي لأضلاع الشجرة الممتدة الدنيا هو $O({\sqrt {n}})$ بعض مجموعات النقاط، مثل النقاط المتباعدة بالتساوي في ${\sqrt {n}}\times {\sqrt {n}}$ ^{[ 12 ]} بالنسبة للنقاط الموجودة في مكعب فائق الوحدة في $d$ في الفضاء ذي الأبعاد n، يكون الحد المقابل هو $O(n^{(d-1)/d})$ [ ²²^{] ينطبق الحد نفسه على الطول الإجمالي} المتوقع للشجرة الممتدة الدنيا لـ $n$ نقاط مختارة بشكل منتظم ومستقل من مربع وحدة أو مكعب فائق وحدة. ^{[ 23 ]} بالعودة إلى مربع الوحدة، فإن مجموع مربعات أطوال حواف الشجرة الممتدة الدنيا هو $O(1)$ يستنتج هذا الحد من ملاحظة أن الحواف لها معينات منفصلة، ومساحتها تتناسب مع مربع طول الحافة. $O({\sqrt {n}})$ يتم تحديد الحد الأقصى للطول الإجمالي عن طريق تطبيق متباينة كوشي-شفارتز . ^{[ 12 ]}

تفسير آخر لهذه النتائج هو أن متوسط طول الحافة لأي مجموعة من النقاط في مربع الوحدة هو $O(1/{\sqrt {n}})$ ، على الأكثر يتناسب مع تباعد النقاط في شبكة منتظمة ؛ وبالنسبة للنقاط العشوائية في مربع وحدة، فإن متوسط الطول يتناسب مع $1/{\sqrt {n}}$ ومع ذلك، في الحالة العشوائية، باحتمالية عالية يكون طول أطول حافة تقريبًا ${\sqrt {\frac {\log n}{\pi n}}},$ أطول من المتوسط بمعامل غير ثابت. باحتمالية عالية، يشكل أطول ضلع ورقة من الشجرة الممتدة، ويربط نقطة بعيدة عن جميع النقاط الأخرى بأقرب جار لها. بالنسبة لأعداد كبيرة من النقاط، يتقارب توزيع طول أطول ضلع حول قيمته المتوقعة إلى توزيع غامبل . ^{[ 24 ]}

أي ممتد هندسي ، وهو رسم بياني فرعي من رسم بياني هندسي كامل، حيث تقارب أقصر مساراته المسافة الإقليدية، يجب أن يكون طول حوافه الكلي مساويًا على الأقل لطول الشجرة الممتدة الدنيا. ومن مقاييس الجودة القياسية للممتد الهندسي النسبة بين طوله الكلي وطول الشجرة الممتدة الدنيا لنفس النقاط. وتحقق عدة طرق لإنشاء الممتدات، مثل الممتد الهندسي الجشع ، حدًا ثابتًا لهذه النسبة. ^{[ 13 ]} وقد تم التكهن بأن نسبة شتاينر ، وهي أكبر نسبة ممكنة بين الطول الكلي للشجرة الممتدة الدنيا وشجرة شتاينر لنفس مجموعة النقاط في المستوى، هي $2/{\sqrt {3}}\approx 1.1547$ ، النسبة لثلاث نقاط في مثلث متساوي الأضلاع . ^{[ 12 ]}

تقسيم فرعي

إذا قُسِّم كل ضلع من أضلاع شجرة الامتداد الأدنى الإقليدية بإضافة نقطة جديدة في منتصفه، فإن الشجرة الناتجة تظل شجرة امتداد أدنى لمجموعة النقاط المُضافة. وتتيح عملية التقسيم هذه إمكانية تقسيم شجرة الامتداد الأدنى الإقليدية بدقة متناهية. مع ذلك، قد يؤدي تقسيم بعض الأضلاع فقط، أو تقسيمها عند نقاط أخرى غير المنتصف، إلى إنتاج مجموعة نقاط لا تكون الشجرة المُقسَّمة عندها هي شجرة الامتداد الأدنى. ^{[ 25 ]}

التعقيد الحسابي

بالنسبة للنقاط في أي بُعد، يمكن إنشاء الشجرة الممتدة الدنيا في وقت $O(n^{2})$ من خلال إنشاء رسم بياني كامل مع وجود حافة بين كل زوج من النقاط، مُرجّحة بالمسافة الإقليدية ، ثم تطبيق خوارزمية شجرة الامتداد الأدنى للرسم البياني مثل خوارزمية بريم-ديكسترا-جارنيك أو خوارزمية بوروفكا عليه. يمكن جعل هذه الخوارزميات تستغرق وقتًا $O(n^{2})$ على عكس خوارزمية كروسكال الشائعة الأخرى، والتي تُعد أبطأ لأنها تتضمن فرز جميع المسافات، فإنها تعمل بشكل أفضل على الرسوم البيانية الكاملة. ^{[ 13 ]} أما بالنسبة للنقاط في الفضاءات منخفضة الأبعاد، فيمكن حل المشكلة بسرعة أكبر، كما هو موضح أدناه.

يتضمن حساب المسافات الإقليدية عملية حساب الجذر التربيعي . عند مقارنة أوزان الحواف، فإن مقارنة مربعات المسافات الإقليدية، بدلاً من المسافات نفسها، تُعطي الترتيب نفسه، وبالتالي لا تُغير بقية حسابات الشجرة. يُسرّع هذا الاختصار الحساب ويسمح بإنشاء شجرة امتداد دنيا للنقاط ذات الإحداثيات الصحيحة باستخدام العمليات الحسابية الصحيحة فقط. ^{[ 20 ]}

بعدين

تعتمد إحدى الطرق الأسرع لإيجاد الشجرة الممتدة الدنيا للنقاط المستوية على خاصية كونها رسمًا بيانيًا فرعيًا من تثليث ديلاوناي:

احسب عملية التثليث ديلاوناي، والتي يمكن القيام بها في $O(n\log n)$ الوقت. ولأن تثليث ديلاوناي عبارة عن رسم بياني مستوٍ ، فإنه يحتوي على أكثر من $3n-6$ الحواف.
قم بتسمية كل ضلع بطوله (المربع).
قم بتشغيل خوارزمية الشجرة الممتدة الدنيا للرسم البياني. نظرًا لوجود $O(n)$ الحواف، وهذا يتطلب $O(n\log n)$ الوقت باستخدام أي من خوارزميات الشجرة الممتدة الدنيا القياسية.

والنتيجة هي خوارزمية تأخذ $O(n\log n)$ الوقت، ^{[ 2 ]} الأمثل في نماذج معينة من الحساب (انظر أدناه ).

إذا كانت إحداثيات الإدخال أعدادًا صحيحة ويمكن استخدامها كمؤشرات للمصفوفة ، فمن الممكن استخدام خوارزميات أسرع: يمكن إنشاء تثليث ديلاوناي بواسطة خوارزمية عشوائية في $O(n\log \log n)$ الوقت المتوقع. ^{[ 26 ]} بالإضافة إلى ذلك، بما أن تثليث ديلاوناي عبارة عن رسم بياني مستوٍ ، فإنه يمكن إيجاد شجرته الممتدة الدنيا في وقت خطي باستخدام صيغة معدلة من خوارزمية بوروفكا التي تزيل جميع الحواف باستثناء الحافة الأرخص بين كل زوج من المكونات بعد كل مرحلة من مراحل الخوارزمية. ^{[ 13 ]}^{[ 27 ]} لذلك، فإن إجمالي الوقت المتوقع لهذه الخوارزمية هو $O(n\log \log n)$ ^{[ 26 ]} في الاتجاه الآخر ، يمكن إنشاء تثليث ديلاوناي من الشجرة الممتدة الدنيا في الحد الزمني شبه الخطي $O(n\log ^{*}n)$ ، أين $\log ^{*}$ [ 28 ]

أبعاد أعلى

ويمكن تعميم المشكلة أيضاً إلى $n$ النقاط في $d$ فضاء ذو أبعاد $\mathbb {R} ^{d}$ في الأبعاد الأعلى، يتم تحديد الاتصال بواسطة تثليث ديلاوناي (الذي يقسم بدوره الغلاف المحدب إلى $d$ تحتوي المضلعات البسيطة ذات الأبعاد n على الشجرة الممتدة الدنيا؛ ومع ذلك، قد يحتوي التثليث على الرسم البياني الكامل. ^{[ 4 ]} لذلك، فإن إيجاد الشجرة الممتدة الدنيا الإقليدية كشجرة ممتدة للرسم البياني الكامل أو كشجرة ممتدة لتثليث ديلاوناي يتطلبان وقتاً طويلاً. $O(dn^{2})$ الزمن. بالنسبة للأبعاد الثلاثة، يمكن إيجاد الشجرة الممتدة الدنيا في الزمن $O{\bigl (}(n\log n)^{4/3}{\bigr )}$ وفي أي بُعد أكبر، في الزمن $O\left(n^{2-{\frac {2}{\lceil d/2\rceil +1}}+\varepsilon }\right)$ لأي $\varepsilon >0$ —أسرع من الحد الزمني التربيعي لخوارزميات الرسم البياني الكامل وتثليث ديلاوناي. ^{[ 4 ]}

لا يزال التعقيد الزمني الأمثل لأشجار الامتداد الأدنى متعددة الأبعاد غير معروف ^{[ 29 ]} ، ولكنه يرتبط ارتباطًا وثيقًا بتعقيد حساب أزواج النقاط الأقرب ثنائية اللون . في مسألة أزواج النقاط الأقرب ثنائية اللون، تكون المدخلات مجموعة من النقاط بلونين مختلفين (مثلاً، الأحمر والأزرق). أما المخرجات فهي زوج من نقطة حمراء ونقطة زرقاء بأقصر مسافة ممكنة. يشكل هذا الزوج دائمًا أحد حواف شجرة الامتداد الأدنى. لذلك، يمكن حل مسألة أزواج النقاط الأقرب ثنائية اللون في نفس الوقت اللازم لإنشاء شجرة الامتداد الأدنى ومسح حوافها بحثًا عن أقصر حافة حمراء-زرقاء. في المقابل، لأي تلوين أحمر-أزرق لأي مجموعة فرعية من مجموعة نقاط معينة، ينتج عن أزواج النقاط الأقرب ثنائية اللون حافة واحدة من شجرة الامتداد الأدنى لتلك المجموعة الفرعية. باختيار تسلسل دقيق لتلوين المجموعات الفرعية، وإيجاد أقرب زوج ثنائي اللون لكل مسألة فرعية، يمكن إيجاد الشجرة الممتدة الدنيا في وقت يتناسب مع الوقت الأمثل لإيجاد أقرب أزواج ثنائية اللون لنفس عدد النقاط، أياً كان هذا الوقت الأمثل. ^{[ 4 ]}^{[ 11 ]}

بالنسبة لمجموعات النقاط العشوائية المنتظمة في أي بُعد محدود، فإن مخطط ياو ^{[ 20 ]} أو تثليث ديلاوناي يتميزان بعدد خطي متوقع من الحواف، ويضمنان احتواء الشجرة الممتدة الدنيا، ويمكن إنشاؤهما في وقت خطي متوقع. ^{[ 21 ]}^{[ 6 ]}^{[ 30 ]} من هذه المخططات، يمكن إنشاء الشجرة الممتدة الدنيا نفسها في وقت خطي، باستخدام خوارزمية عشوائية خطية الوقت للأشجار الممتدة الدنيا للمخططات . ^{[ 31 ]} ومع ذلك، فإن الأداء الضعيف لهذه الطرق على المدخلات القادمة من البيانات المجمعة قد دفع باحثي هندسة الخوارزميات إلى تطوير طرق أبطأ نوعًا ما. $O(n\log n)$ محدد زمنيًا، للمدخلات العشوائية أو المدخلات التي تشبه مسافاتها وتجميعها تلك الخاصة بالبيانات العشوائية، مع إظهار أداء أفضل على بيانات العالم الحقيقي. ^{[ 8 ]}^{[ 32 ]}^{[ 5 ]}

يُعرَّف تحليل الأزواج المنفصلة جيدًا بأنه مجموعة من أزواج المجموعات الجزئية للنقاط المعطاة، بحيث ينتمي كل زوج من النقاط إلى أحد هذه الأزواج، وتكون جميع أزواج النقاط التي تنتمي إلى نفس الزوج من المجموعات الجزئية متساوية الطول تقريبًا. من الممكن إيجاد تحليل أزواج منفصل جيدًا بعدد خطي من المجموعات الجزئية، وزوج نقاط تمثيلي لكل مجموعة جزئية، في زمن زمني قدره 1/2. $O(n\log n)$ تُعدّ الشجرة الممتدة الدنيا للرسم البياني المُشكّل من هذه الأزواج التمثيلية تقريبًا للشجرة الممتدة الدنيا. وباستخدام هذه الأفكار، $(1+\varepsilon )$ يمكن إيجاد تقريب لأدنى شجرة ممتدة في $O(n\log n)$ الوقت، من أجل ثابت $\varepsilon$ وبشكل أدق، من خلال اختيار كل زوج تمثيلي لتقريب أقرب زوج في فئة التكافؤ الخاصة به ، وتغيير جودة هذا التقريب بعناية للأزواج المختلفة، فإن الاعتماد على $\varepsilon$ يمكن تحديد المدة الزمنية على النحو التالي: $O(n\log n+(\varepsilon ^{-2}\log ^{2}{\tfrac {1}{\varepsilon }})n),$ لأي بُعد ثابت. ^{[ 33 ]}

ديناميكي وحركي

تم تعميم شجرة الامتداد الأدنى الإقليدية بطرق عديدة ومختلفة لتشمل أنظمة النقاط المتحركة أو المتغيرة:

إذا خضعت مجموعة من النقاط لسلسلة من عمليات الإضافة أو الحذف الديناميكية، فإن كل تحديث من هذه التحديثات يُحدث تغييرًا محدودًا في الشجرة الممتدة الدنيا لهذه النقاط. عندما تكون سلسلة التحديثات معروفة مسبقًا، بالنسبة للنقاط الموجودة في المستوى، يمكن إيجاد التغيير بعد كل إضافة أو حذف في الزمن. $O(\log ^{2}n)$ لكل عملية إدراج أو حذف. ^{[ 34 ]} عندما يجب معالجة التحديثات عبر الإنترنت ، يكون ذلك أبطأ (ولكنه لا يزال متعدد اللوغاريتمات) $O(\log ^{10}n)$ الحد الزمني معروف. ^{[ 35 ]} بالنسبة للإصدارات ذات الأبعاد الأعلى من المسألة، يكون الوقت اللازم لكل تحديث أبطأ، ولكنه لا يزال دون الخطي. ^{[ 36 ]}
ل $n$ عند تحريك النقاط بشكل خطي بسرعة ثابتة، أو عند القيام بحركات جبرية أكثر عمومية، يتغير الحد الأدنى للشجرة الممتدة بسلسلة من عمليات التبديل، حيث تُزال حافة وتُستبدل بأخرى عند نقطة زمنية يكون فيها طول كلتا الحافتين متساوياً. ^{[ 37 ]} بالنسبة للحركات الخطية، يكون عدد التغييرات أكبر بقليل من $n^{25/9}$ [ ³⁸^] بالنسبة للحركات الجبرية الأكثر عمومية، يوجد حد أعلى شبه مكعب لعدد عمليات التبديل، استنادًا إلى نظرية ^{متواليات} دافنبورت-شينزل . ^[³⁹^]
تتعلق مسألة الشجرة الممتدة المتحركة الدنيا بنقاط تتحرك خطيًا بسرعة ثابتة، خلال فترة زمنية محددة، وتسعى إلى إيجاد شجرة واحدة تُقلل من مجموع الأوزان الأقصى في أي لحظة خلال هذه الفترة. يُعد حسابها بدقة مسألة صعبة حسابيًا (NP-hard) ، ولكن يمكن تقريبها بدقة تصل إلى عامل اثنين في وقت متعدد الحدود. ^{[ 40 ]}
تتطلب مسألة الشجرة الممتدة الدنيا الإقليدية الحركية بنية بيانات حركية قادرة على الحفاظ على الشجرة الممتدة الدنيا أثناء تحرك نقاطها بشكل مستمر، بالإضافة إلى عمليات الإضافة والحذف. وقد تناولت عدة أبحاث هذه البنى، ^{[ 41 ]}^{[ 42 ]}^{[ 43 ]}^[⁴⁴^]^[⁴⁵^] ، كما عُرفت بنية حركية للنقاط المتحركة جبريًا بزمن إجمالي شبه مكعب، يكاد يطابق الحد الأقصى لعدد عمليات التبديل. ^{[ 44 ]}

الحد الأدنى

حد أدنى تقاربي لـ $\Omega (n\log n)$ يمكن إيجاد حلول لمشكلة الشجرة الممتدة الدنيا الإقليدية في نماذج حسابية مقيدة. تشمل هذه النماذج شجرة القرار الجبرية وشجرة الحساب الجبرية ، حيث لا يمكن للخوارزمية الوصول إلى نقاط الإدخال إلا من خلال عناصر أولية مقيدة تُجري عمليات حسابية جبرية بسيطة على إحداثياتها. في هذه النماذج، تتطلب مشكلة أقرب زوج من النقاط $\Omega (n\log n)$ يستغرق الأمر وقتًا، ولكن أقرب زوج هو بالضرورة حافة من الشجرة الممتدة الدنيا، لذا فإن الشجرة الممتدة الدنيا تتطلب أيضًا هذا القدر من الوقت. لذلك، فإن الخوارزميات لإنشاء الشجرة الممتدة الدنيا المستوية في وقت $O(n\log n)$ في هذا النموذج، على سبيل المثال باستخدام تثليث ديلاوناي، تكون الحلول الأمثل. ^{[ 46 ]} مع ذلك، لا تنطبق هذه الحدود الدنيا على نماذج الحساب ذات إحداثيات النقاط الصحيحة، حيث يُسمح بعمليات البت وعمليات فهرسة الجداول على تلك الإحداثيات. في هذه النماذج، يمكن استخدام خوارزميات أسرع، كما هو موضح أعلاه. ^{[ 26 ]}

التطبيقات

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

ترتبط الأشجار الممتدة الدنيا ارتباطًا وثيقًا بالتجميع أحادي الارتباط ، وهو أحد أساليب التجميع الهرمي . تُحدد حواف الشجرة الممتدة الدنيا، مرتبةً حسب طولها، ترتيب دمج المجموعات في مجموعات أكبر في هذا الأسلوب. وبمجرد العثور على هذه الحواف، باستخدام أي خوارزمية، يمكن استخدامها لإنشاء التجميع أحادي الارتباط في الزمن. $O(n\log n)$ [ ^{1 ]}^{على الرغم من أن} أشكال التجمعات الطويلة والرفيعة الناتجة عن التجميع أحادي الارتباط قد لا تتناسب مع أنواع معينة من البيانات، مثل مخاليط التوزيعات الغاوسية ، إلا أنها قد تكون خيارًا جيدًا في التطبيقات التي يُتوقع فيها أن تتخذ التجمعات نفسها أشكالًا طويلة ورفيعة، كما هو الحال في نمذجة هالات المادة المظلمة للمجرات . ^{[ 5 ]} في علم المعلومات الجغرافية ، استخدمت العديد من مجموعات الباحثين أشجار الامتداد الأدنى لمراكز المباني لتحديد تجمعات ذات دلالة من المباني، على سبيل المثال عن طريق إزالة الحواف التي تم تحديدها بطريقة أخرى على أنها غير متسقة. ^{[ 49 ]}

استُخدمت الأشجار الممتدة الدنيا أيضًا لاستنتاج شكل المنحنيات في المستوى، انطلاقًا من نقاط مُختارة على طول المنحنى. بالنسبة لمنحنى أملس، مُختار بدقة أكبر من حجم ميزته المحلية ، تُشكّل الشجرة الممتدة الدنيا مسارًا يربط النقاط المتتالية على طول المنحنى. وبشكل أعم، تستطيع طرق مماثلة التعرّف على المنحنيات المرسومة بأسلوب منقط أو متقطع بدلًا من كونها مجموعة متصلة واحدة. تشمل تطبيقات هذه التقنية في إيجاد المنحنيات فيزياء الجسيمات ، في التعرّف التلقائي على المسارات التي تتركها الجسيمات في حجرة الفقاعات . ^{[ 50 ]} يمكن لإصدارات أكثر تطورًا من هذه الفكرة إيجاد المنحنيات من سحابة من نقاط العينة المشوّشة التي تتبع تقريبًا محيط المنحنى، وذلك باستخدام طوبولوجيا الشجرة الممتدة لتوجيه طريقة المربعات الصغرى المتحركة . ^{[ 51 ]}

من التطبيقات الأخرى للأشجار الممتدة الدنيا خوارزمية تقريب ذات عامل ثابت لمسألة البائع المتجول الإقليدية ، وهي مسألة إيجاد أقصر مضلع لمجموعة نقاط. يمكن للمشي حول حدود الشجرة الممتدة الدنيا تقريب مسار البائع المتجول الأمثل بمعامل اثنين من الطول الأمثل. ^{[ 2 ]} مع ذلك، توجد مخططات تقريب أكثر دقة ذات زمن متعدد الحدود لهذه المسألة. ^{[ 52 ]} في الشبكات اللاسلكية المخصصة ، يمكن أن يكون بث الرسائل على طول مسارات في شجرة ممتدة دنيا تقريبًا دقيقًا لتوجيه البث ذي الطاقة الدنيا، والذي يصعب حسابه بدقة. ^{[ 53 ]}^{[ 54 ]}^{[ 55 ]}^{[ 56 ]}

تحقيق

تأخذ مسألة تحقيق الأشجار الممتدة الدنيا الإقليدية شجرة مجردة كمدخل، وتبحث عن موقع هندسي لكل رأس من رؤوس الشجرة (في فضاء ذي بُعد ثابت)، بحيث تكون الشجرة المعطاة مساوية للشجرة الممتدة الدنيا لتلك النقاط. لا تمتلك كل شجرة مجردة مثل هذا التحقيق؛ على سبيل المثال، يجب أن تلتزم الشجرة بحدود عدد التقبيل على درجة كل رأس. توجد قيود إضافية؛ على سبيل المثال، لا يمكن لشجرة ممتدة دنيا مستوية أن تحتوي على رأس من الدرجة السادسة مجاور لرأس من الدرجة الخامسة أو السادسة. ^{[ 7 ]} يُعد تحديد ما إذا كان هناك تحقيق ثنائي الأبعاد مسألة صعبة من نوع NP . ومع ذلك، يعتمد إثبات صعوبة المسألة على حقيقة أن الرؤوس من الدرجة السادسة في الشجرة لها مجموعة محدودة للغاية من التحقيقات: يجب وضع جيران هذا الرأس على رؤوس سداسي منتظم مركزه ذلك الرأس. ^{[ 57 ]} في الواقع، بالنسبة للأشجار ذات الدرجة القصوى الخامسة، يوجد دائمًا تحقيق مستوٍ. ^{[ 7 ]} وبالمثل، بالنسبة للأشجار ذات الدرجة القصوى عشرة، يوجد دائمًا تمثيل ثلاثي الأبعاد. ^{[ 10 ]} بالنسبة لهذه التمثيلات، قد تتطلب بعض الأشجار حوافًا ذات طول أُسّي ومربعات محيطة ذات مساحة أُسّية نسبةً إلى طول أقصر حافة فيها. ^{[ 58 ]} أما الأشجار ذات الدرجة القصوى أربعة فلها تمثيلات مستوية أصغر، بأطوال حواف ومربعات محيطة محدودة كثير الحدود. ^{[ 9 ]}

انظر أيضاً

شجرة الامتداد الأدنى المستقيمة ، وهي شجرة امتداد أدنى تُقاس مسافاتها باستخدام هندسة سيارات الأجرة.

مراجع

1 2 غاور، جيه سي؛ روس، جي جي إس (1969)، "أشجار الامتداد الأدنى وتحليل التجميع بالارتباط الأحادي"، الإحصاء التطبيقي ، 18 (1): 54-61 ، doi : 10.2307/2346439 ، JSTOR 2346439 ، MR 0242315
1 2 3 4 شاموس، مايكل إيان ؛ هوي، دان (1975)، "مسائل أقرب نقطة"، الندوة السنوية السادسة عشرة حول أسس علوم الحاسوب، بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية، 13-15 أكتوبر 1975 ، جمعية مهندسي الكهرباء والإلكترونيات، ص 151-162 ، doi : 10.1109/SFCS.1975.8 ، MR 0426498 ، S2CID 40615455
↑ بوز، بروسنجيت ؛ ديفروي، لوك ؛ إيفانز، ويليام؛ كيركباتريك، ديفيد (2006)، "حول نسبة الامتداد لرسوم غابرييل والهياكل العظمية بيتا"، مجلة SIAM للرياضيات المتقطعة ، 20 (2): 412-427 ، doi : 10.1137/S0895480197318088 ، MR 2257270
1 2 3 4 أغاروال، ب.ك .؛ إيدلسبرونر، هـ .؛ شوارزكوف، أ .؛ ويلزل، إ. (1991)، "أشجار الامتداد الدنيا الإقليدية وأقرب الأزواج ثنائية اللون"، الهندسة المنفصلة والحسابية ، 6 (1)، سبرينغر: 407-422 ، doi : 10.1007/BF02574698 ، MR 1115099
1 2 3 مارس، ويليام ب.؛ رام، باريكشيت؛ غراي، ألكسندر ج. (2010)، "شجرة الامتداد الدنيا الإقليدية السريعة: الخوارزمية والتحليل والتطبيقات"، في راو، بهارات؛ كريشنابورام، بالاجي؛ تومكينز، أندرو؛ يانغ، تشيانغ (محررون)، وقائع المؤتمر الدولي السادس عشر لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات، واشنطن العاصمة، الولايات المتحدة الأمريكية، 25-28 يوليو 2010، الصفحات 603-612 ، doi : 10.1145/1835804.1835882 ، S2CID 186025
1 2 كلاركسون، كينيث ل. (1989)، "خوارزمية للأشجار الممتدة الدنيا الهندسية تتطلب وقتًا متوقعًا خطيًا تقريبًا"، Algorithmica ، 4 ( 1-4 ): 461-469 ، doi : 10.1007/BF01553902 ، MR 1019387 ، S2CID 22176641
1 2 3 4 مونما، كلايد؛ سوري، سوبهاش (1992)، "الانتقالات في الأشجار الممتدة الدنيا الهندسية"، الهندسة المنفصلة والحسابية ، 8 (3): 265-293 ، doi : 10.1007/BF02293049 ، MR 1174358 ، S2CID 30101649
1 2 ناراسيمهان، جيري؛ زاكارياسن، مارتن؛ تشو، جيانلين ( 2000)، "تجارب في حساب الأشجار الممتدة الدنيا الهندسية"، وقائع ورشة العمل الثانية حول هندسة الخوارزميات والتجارب ، ص 183-196
1 2 فراتي، فابريزيو؛ كوفمان، مايكل (2011)، "حدود مساحة متعددة الحدود لتضمينات MST للأشجار"، الهندسة الحسابية: النظرية والتطبيقات ، 44 (9): 529-543 ، doi : 10.1016/j.comgeo.2011.05.005 ، MR 2819643 ، S2CID 5634139
1 2 كينغ، جيمس أ. (2006)، "تحقيق الأشجار الممتدة الدنيا من الدرجة 10 في الفضاء ثلاثي الأبعاد" (ملف PDF) ، وقائع المؤتمر الكندي السنوي الثامن عشر للهندسة الحسابية، CCCG 2006، 14-16 أغسطس 2006، جامعة كوينز، أونتاريو، كندا ، الصفحات 39-42
1 2 كرزناريتش، دراغو؛ ليفكوبولوس، كريستوس؛ نيلسون، بينجت ج. (1999)، “الحد الأدنى من الأشجار الممتدة في $d$ الأبعاد"، المجلة الإسكندنافية للحوسبة ، 6 (4): 446-461 ، MR 1736451 هذه النسخة من هذه الورقة غير متاحة عبر الإنترنت؛ بدلاً من ذلك، انظر نسخة المؤتمر لعام 1997 من نفس الورقة، doi : 10.1007/3-540-63397-9_26 .
1 2 3 4 5 6 7 جيلبرت، إي إن ؛ بولاك، إتش أو (1968)، "أشجار شتاينر الدنيا"، مجلة SIAM للرياضيات التطبيقية ، 16 (1): 1-29 ، doi : 10.1137/0116001 ، JSTOR 2099400 ، MR 0223269
1 2 3 4 إبستين، ديفيد (1999)، "الأشجار الممتدة والممتدات" (ملف PDF) ، في ساك، جيه.-آر .؛ أوروتيا، جيه. (محرران)، دليل الهندسة الحسابية ، إلسيفير، الصفحات 425-461 ، MR 1746681
^ جورجاكوبولوس، جورج. Papadimitriou، Christos H. (1987)، “The 1-Steiner Tree مشكلة”، مجلة الخوارزميات ، 8 (1): 122–130 ، دوى : 10.1016 / 0196-6774(87)90032-0 ، MR 0875330
1 2 روبنز، جي.؛ سالو، جيه إس (1995)، "الأشجار الممتدة الدنيا منخفضة الدرجة"، الهندسة المنفصلة والحسابية ، 14 (2): 151-165 ، doi : 10.1007/BF02570700 ، MR 1331924 ، S2CID 16040977
↑ بفندر، فلوريان؛ زيغلر، غونتر م. ( سبتمبر 2004)، "أعداد التقبيل، وتعبئة الكرات، وبعض البراهين غير المتوقعة" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية : 873-883
↑ ستيل، ج. مايكل ؛ شيب، لورانس أ.؛ إيدي، ويليام ف. (1987)، "حول عدد أوراق الشجرة الممتدة الدنيا الإقليدية"، مجلة الاحتمالات التطبيقية ، 24 (4): 809-826 ، doi : 10.2307/3214207 ، JSTOR 3214207 ، MR 0913823 ، S2CID 29026025
↑ بريباراتا، فرانكو ب .؛ شاموس، مايكل إيان (1985)، الهندسة الحسابية: مقدمة ، نصوص ودراسات في علوم الحاسوب، سبرينغر-فيرلاغ، نيويورك، ص 263، doi : 10.1007/978-1-4612-1098-6 ، ISBN 0-387-96131-3، MR 0805539 ، S2CID 206656565
↑ توسان، جي تي (1980)، "تعليق: خوارزميات لحساب الرسم البياني للجوار النسبي"، رسائل الإلكترونيات ، 16 (22): 860، رمز Bibcode : 1980ElL....16..860T ، doi : 10.1049/el:19800611 رد أوركهارت، الصفحات 860-861
1 2 3 ياو، أندرو تشي تشيه (1982)، "حول بناء الأشجار الممتدة الدنيا في الفضاءات ذات الأبعاد $k$ والمشاكل ذات الصلة"، مجلة SIAM للحوسبة ، 11 (4): 721-736 ، doi : 10.1137/0211059 ، MR 0677663
1 2 بنتلي، جون لويس ؛ وايد، بروس دبليو؛ ياو، أندرو سي (1980)، "خوارزميات الوقت المتوقع الأمثل لمسائل أقرب نقطة" ، معاملات ACM في البرمجيات الرياضية ، 6 (4): 563-580 ، doi : 10.1145/355921.355927 ، MR 0599977 ، S2CID 17238717
↑ ستيل، ج. مايكل ؛ سنايدر، تيموثي لو (1989)، "معدلات النمو في أسوأ الحالات لبعض المسائل الكلاسيكية في التحسين التوافقي" ، مجلة SIAM للحوسبة ، 18 (2): 278-287 ، doi : 10.1137/0218019 ، MR 0986667
↑ ستيل، ج. مايكل (1988)، "معدلات نمو الأشجار الممتدة الدنيا الإقليدية ذات الحواف الموزونة بالقوة"، حوليات الاحتمالات ، 16 (4): 1767-1787 ، doi : 10.1214/aop/1176991596 ، JSTOR 2243991 ، MR 0958215
↑ بينروز، ماثيو د. (1997)، "أطول حافة في الشجرة الممتدة الدنيا العشوائية"، حوليات الاحتمالات التطبيقية ، 7 (2): 340-361 ، doi : 10.1214/aoap/1034625335 ، MR 1442317
↑ بويس، دبليو إم؛ غاري، إم آر ؛ جونسون، دي إس (1978)، "ملاحظة حول تنصيف الأشجار الممتدة الدنيا"، الشبكات ، 8 (3): 187-192 ، doi : 10.1002/net.3230080302 ، MR 0491324
1 2 3 بوتشين، كيفن؛ مولزر، وولفغانغ (2011)، "تثليثات ديلاوناي في زمن $O$ (sort( $n$ )) وأكثر"، مجلة ACM ، 58 (2): A6:1–A6:27، doi : 10.1145/1944345.1944347 ، MR 2786587 ، S2CID 11316974
↑ ماريس، مارتن (2004)، "خوارزميتان خطيتان لإيجاد الشجرة الممتدة الدنيا على فئات الرسوم البيانية المغلقة الصغرى" (ملف PDF) ، أرشيف الرياضيات ، 40 (3): 315-320 ، MR 2107027
↑ ديفيليرز، أوليفييه (1992)، "التوزيع العشوائي يُنتج خوارزميات بسيطة من رتبة $O$ $($ $n$ $log$ $*$ $n) لمسائل$ $Ω$ $($ $n$ $)$ الصعبة " (ملف PDF) ، المجلة الدولية للهندسة الحسابية والتطبيقات ، 2 (1): 97-111 ، doi : 10.1142/S021819599200007X ، MR 1159844 ، S2CID 60203
↑ أورورك، ج .؛ ديمين، إ. (2001-2002)، "المسألة 5: الشجرة الممتدة الدنيا الإقليدية" ، مشروع المسائل المفتوحة ، كلية سميث
↑ دواير، ريكس أ. (1991)، "مخططات فورونوي متعددة الأبعاد في زمن متوقع خطي"، الهندسة المنفصلة والحسابية ، 6 (4): 343-367 ، doi : 10.1007/BF02574694 ، MR 1098813
↑ كارغر، ديفيد ر.؛ كلاين، فيليب ن.؛ تارجان، روبرت إي. (1995)، "خوارزمية عشوائية خطية لإيجاد الأشجار الممتدة الدنيا"، مجلة ACM ، 42 (2): 321-328 ، doi : 10.1145/201019.201022 ، MR 1409738 ، S2CID 832583
↑ تشاتيرجي، س.؛ كونور، م.؛ كومار، ب. (2010)، "الأشجار الممتدة الدنيا الهندسية باستخدام GeoFilterKruskal"، في فيستا، باولا (محرر)، الخوارزميات التجريبية: الندوة الدولية التاسعة، SEA 2010، جزيرة إيشيا، نابولي، إيطاليا، 20-22 مايو 2010، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 6049، سبرينغر-فيرلاغ، الصفحات 486-500 ، doi : 10.1007/978-3-642-13193-6_41 ، ISBN 978-3-642-13192-9
↑ آريا، سونيل؛ ماونت، ديفيد م. (2016)، "خوارزمية سريعة وبسيطة لحساب الأشجار الممتدة الدنيا الإقليدية التقريبية"، في كراوثغامر، روبرت (محرر)، وقائع الندوة السنوية السابعة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة، SODA 2016، أرلينغتون، فيرجينيا، الولايات المتحدة الأمريكية، 10-12 يناير 2016، الصفحات 1220-1233 ، doi : 10.1137/1.9781611974331.ch85 ، ISBN 978-1-61197-433-1، MR 3478461
↑ إبستين، ديفيد (1994)، "خوارزميات غير متصلة بالإنترنت لمسائل الشجرة الممتدة الدنيا الديناميكية" ، مجلة الخوارزميات ، 17 (2): 237-250 ، doi : 10.1006/jagm.1994.1033 ، MR 1291541
↑ تشان، تيموثي م. (2010)، "بنية بيانات ديناميكية للأغلفة المحدبة ثلاثية الأبعاد واستعلامات أقرب جار ثنائية الأبعاد"، مجلة ACM ، 57 (3): المقالة 16، doi : 10.1145/1706591.1706596 ، MR 2665885 ، S2CID 47454142
↑ إبستين، ديفيد (1995)، "الأشجار الممتدة الدنيا الإقليدية الديناميكية والقيم القصوى للدوال الثنائية"، الهندسة المنفصلة والحسابية ، 13 (1): 111-122 ، doi : 10.1007/BF02574030 ، MR 1300511 ، S2CID 7339165
↑ كاتوه، ن.؛ توكوياما، ت.؛ إيوانو، ك. (1995)، "حول الأشجار الممتدة الدنيا والقصوى للنقاط المتحركة خطيًا"، الهندسة المنفصلة والحسابية ، 13 (2): 161-176 ، doi : 10.1007/BF02574035 ، MR 1314960
↑ تشان، تيموثي م. (2003)، "حول المستويات في ترتيبات المنحنيات"، الهندسة المنفصلة والحسابية ، 29 (3): 375-393 ، doi : 10.1007/s00454-002-2840-2 ، MR 1961005 ، S2CID 18966889
↑ رحمتي، زاهد؛ زارعي، علي رضا (2010)، "التغييرات التوافقية للشجرة الممتدة الدنيا الإقليدية للنقاط المتحركة في المستوى" (ملف PDF) ، وقائع المؤتمر الكندي السنوي الثاني والعشرين للهندسة الحسابية، وينيبيغ، مانيتوبا، كندا، 9-11 أغسطس 2010 ، ص 43-45
↑ أكيتيا، هوغو أ.؛ بينياز، أحمد؛ بوس، بروسنجيت ؛ دي كاروفيل، جان لو؛ ماهيشواري، أنيل؛ دا سيلفيرا، لويس فرناندو شولتز خافيير؛ سميد، ميشيل (2021)، "مسألة الشجرة الممتدة المتحركة الدنيا"، في لوبيو، آنا ؛ سالافاتيبور، محمد ر. (محرران)، الخوارزميات وهياكل البيانات: الندوة الدولية السابعة عشرة، WADS 2021، حدث افتراضي، 9-11 أغسطس 2021، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 12808، سبرينغر، الصفحات 15-28 ، doi : 10.1007/978-3-030-83508-8_2 ، ISBN 978-3-030-83507-1، S2CID 234599877
↑ باش، جوليان؛ غيباس، ليونيداس ج .؛ تشانغ، لي (1997)، "مسائل التقارب على النقاط المتحركة"، في بويسونات، جان-دانيال (محرر)، وقائع الندوة السنوية الثالثة عشرة حول الهندسة الحسابية، نيس، فرنسا، 4-6 يونيو 1997 ، رابطة آلات الحوسبة، ص 344-351 ، doi : 10.1145/262839.262998 ، ISBN 0-89791-878-9، S2CID 15556637
↑ أغاروال، بانكاج ك .؛ إبستين، ديفيد ؛ غيباس، ليونيداس ج .؛ هينزينغر، مونيكا راوخ (1998)، "الأشجار الممتدة الدنيا البارامترية والحركية"، الندوة السنوية التاسعة والثلاثون حول أسس علوم الحاسوب، FOCS '98، 8-11 نوفمبر 1998، بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية (ملف PDF) ، جمعية IEEE للحاسوب، الصفحات 596-605 ، doi : 10.1109/SFCS.1998.743510 ، ISBN 0-8186-9172-7، S2CID 2559456
↑ رحمتي، زاهد؛ زارعي، علي رضا (2012)، "شجرة الامتداد الأدنى الإقليدية الحركية في المستوى"، مجلة الخوارزميات المنفصلة ، 16 : 2-11 ، doi : 10.1016/j.jda.2012.04.009 ، MR 2960341
1 2 رحمتي، زاهد؛ أبام، محمد علي؛ كينغ، فاليري ؛ وايتسايدز، سو ؛ زارعي، علي رضا (2015)، "طريقة بسيطة وأسرع لمسائل التقارب الحركي"، الهندسة الحسابية: النظرية والتطبيقات ، 48 (4): 342-359 ، arXiv : 1311.2032 ، doi : 10.1016/j.comgeo.2014.12.002 ، MR 3296072 ، S2CID 18971251
↑ ميولمانز، ووتر؛ سبيكمان، بيتينا ؛ فيربيك، كيفن؛ وولمز، جولز (2018)، "إطار عمل لاستقرار الخوارزميات وتطبيقه على أشجار الامتداد الدنيا الإقليدية الحركية"، في بيندر، مايكل أ.؛ فاراش-كولتون، مارتن ؛ موستيرو، ميغيل أ. (محررون)، LATIN 2018: المعلوماتية النظرية - الندوة اللاتينية الأمريكية الثالثة عشرة، بوينس آيرس، الأرجنتين، 16-19 أبريل 2018، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 10807، سبرينغر، الصفحات 805-819 ، doi : 10.1007/978-3-319-77404-6_58 ، ISBN 978-3-319-77403-9، S2CID 4709616
↑ ياو، أندرو تشي-تشيه (1991)، "الحدود الدنيا لأشجار الحساب الجبري ذات المدخلات الصحيحة"، مجلة SIAM للحوسبة ، 20 (4): 655-668 ، doi : 10.1137/0220041 ، MR 1105929
↑ غراهام، آر إل ؛ هيل، بافول (1985)، "حول تاريخ مشكلة الشجرة الممتدة الدنيا"، حوليات IEEE لتاريخ الحوسبة ، 7 (1): 43-57 ، doi : 10.1109/mahc.1985.10011 ، MR 0783327 ، S2CID 10555375
↑ لوبرمان، هـ.؛ واينبرغر، أ. (أكتوبر 1957)، "إجراءات رسمية لتوصيل الأطراف بأقل طول إجمالي للسلك"، مجلة ACM ، 4 (4): 428-437 ، doi : 10.1145/320893.320896 ، S2CID 7320964
^ وو بن. يو، بيلانج؛ وو، تشيوشنغ؛ تشن، زوقي. ياو، شنجون؛ هوانغ، يان. وو، جيان بينغ (أكتوبر 2017)، “طريقة الحد الأدنى الممتد للشجرة الممتدة لتوصيف الأنماط الحضرية المحلية”، المجلة الدولية لعلوم المعلومات الجغرافية ، 32 (3): 450-475 ، دوى : 10.1080/13658816.2017.1384830 ، S2CID 46772272
↑ زان، سي تي (1973)، "استخدام الشجرة الممتدة الدنيا للتعرف على المنحنيات المنقطة والمتقطعة" ، الندوة الدولية الأولى للحوسبة، دافوس، سويسرا، 4-7 سبتمبر 1973
↑ لي، إن-كوون (2000)، "إعادة بناء المنحنى من نقاط غير منظمة"، التصميم الهندسي بمساعدة الحاسوب ، 17 (2): 161-177 ، CiteSeerX 10.1.1.56.1432 ، doi : 10.1016/S0167-8396(99)00044-8 ، MR 1733203
↑ بارتال، يائير؛ غوتليب، لي-آد (2013)، "مخطط تقريب زمني خطي لمسألة البائع المتجول الإقليدية"، المؤتمر السنوي الرابع والخمسون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، FOCS 2013، 26-29 أكتوبر 2013، بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية ، الصفحات 698-706 ، CiteSeerX 10.1.1.409.1291 ، doi : 10.1109/FOCS.2013.80 ، ISBN 978-0-7695-5135-7، MR 3246273 ، S2CID 17514182
↑ وان، ب.-ج.؛ كالينسكو، ج.؛ لي، إكس.-واي.؛ فريدر، أ. (2002)، "البث بأقل طاقة في الشبكات اللاسلكية الثابتة المخصصة"، الشبكات اللاسلكية ، 8 (6): 607-617 ، doi : 10.1023/a:1020381720601 ، S2CID 1297518
↑ كليمنتي، أندريا إي إف؛ هويبان، غورفان؛ روسي، جيانلوكا؛ فيرهوفن، يان سي؛ بينا، باولو (2003)، "حول نسبة التقريب للطريقة الاستدلالية القائمة على شجرة الامتداد الأدنى لمشكلة البث الموفر للطاقة في شبكات الراديو الثابتة المخصصة"، المؤتمر الدولي السابع عشر للمعالجة المتوازية والموزعة (IPDPS 2003)، 22-26 أبريل 2003، نيس، فرنسا، وقائع المؤتمر ، جمعية مهندسي الكهرباء والإلكترونيات، ص 222، doi : 10.1109/IPDPS.2003.1213407 ، ISBN 0-7695-1926-1، S2CID 17863487
↑ فلاميني، ميشيل؛ كلاسينغ، رالف؛ نافارا، ألفريدو؛ بيرينيس، ستيفان (2007)، "نتائج تقريبية محسّنة لمسألة بث الطاقة الدنيا"، Algorithmica ، 49 (4): 318-336 ، doi : 10.1007/s00453-007-9077-7 ، MR 2358524 ، S2CID 11982404
↑ أمبوهل، كريستوف (2005)، "حد أمثل لخوارزمية MST لحساب أشجار البث الموفرة للطاقة في الشبكات اللاسلكية"، في كايريس، لويس؛ إيتاليانو، جوزيبي ف .؛ مونتيرو، لويس؛ بالاميديسي، كاتوسيا ؛ يونغ، موتي (محررون)، الأوتوماتا واللغات والبرمجة، الندوة الدولية الثانية والثلاثون، ICALP 2005، لشبونة، البرتغال، 11-15 يوليو 2005، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 3580، سبرينغر، الصفحات 1139-1150 ، doi : 10.1007/11523468_92 ، ISBN 978-3-540-27580-0
↑ إيدز، بيتر ؛ وايتسايدز، سو (1996)، "مشكلة تحقيق الأشجار الممتدة الدنيا الإقليدية هي مسألة صعبة من نوع NP"، Algorithmica ، 16 (1): 60-82 ، doi : 10.1007/s004539900037 ، MR 1394494
↑ أنجيليني، باتريزيو؛ بروكدورفر، تيل؛ كييزا، ماركو؛ فراتي، فابريزيو؛ كوفمان، مايكل؛ سكوارسيلا، كلاوديو (2014)، "حول متطلبات مساحة الأشجار الممتدة الدنيا الإقليدية"، الهندسة الحسابية: النظرية والتطبيقات ، 47 (2، الجزء ب): 200-213 ، doi : 10.1016/j.comgeo.2012.10.011 ، MR 3123788

روابط خارجية

البرنامج التعليمي لـEMST ، ووثائق mlpack

[gowros-1] 1 2 غاور، جيه سي؛ روس، جي جي إس (1969)، "أشجار الامتداد الأدنى وتحليل التجميع بالارتباط الأحادي"، الإحصاء التطبيقي ، 18 (1): 54-61 ، doi : 10.2307/2346439 ، JSTOR 2346439 ، MR 0242315

[shahoe-2] 1 2 3 4 شاموس، مايكل إيان ؛ هوي، دان (1975)، "مسائل أقرب نقطة"، الندوة السنوية السادسة عشرة حول أسس علوم الحاسوب، بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية، 13-15 أكتوبر 1975 ، جمعية مهندسي الكهرباء والإلكترونيات، ص 151-162 ، doi : 10.1109/SFCS.1975.8 ، MR 0426498 ، S2CID 40615455

[bdek-3] بوز، بروسنجيت ؛ ديفروي، لوك ؛ إيفانز، ويليام؛ كيركباتريك، ديفيد (2006)، "حول نسبة الامتداد لرسوم غابرييل والهياكل العظمية بيتا"، مجلة SIAM للرياضيات المتقطعة ، 20 (2): 412-427 ، doi : 10.1137/S0895480197318088 ، MR 2257270

[aesw-4] 1 2 3 4 أغاروال، ب.ك .؛ إيدلسبرونر، هـ .؛ شوارزكوف، أ .؛ ويلزل، إ. (1991)، "أشجار الامتداد الدنيا الإقليدية وأقرب الأزواج ثنائية اللون"، الهندسة المنفصلة والحسابية ، 6 (1)، سبرينغر: 407-422 ، doi : 10.1007/BF02574698 ، MR 1115099

[mrg-5] 1 2 3 مارس، ويليام ب.؛ رام، باريكشيت؛ غراي، ألكسندر ج. (2010)، "شجرة الامتداد الدنيا الإقليدية السريعة: الخوارزمية والتحليل والتطبيقات"، في راو، بهارات؛ كريشنابورام، بالاجي؛ تومكينز، أندرو؛ يانغ، تشيانغ (محررون)، وقائع المؤتمر الدولي السادس عشر لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات، واشنطن العاصمة، الولايات المتحدة الأمريكية، 25-28 يوليو 2010، الصفحات 603-612 ، doi : 10.1145/1835804.1835882 ، S2CID 186025

[clarkson-6] 1 2 كلاركسون، كينيث ل. (1989)، "خوارزمية للأشجار الممتدة الدنيا الهندسية تتطلب وقتًا متوقعًا خطيًا تقريبًا"، Algorithmica ، 4 ( 1-4 ): 461-469 ، doi : 10.1007/BF01553902 ، MR 1019387 ، S2CID 22176641

[monsur-7] 1 2 3 4 مونما، كلايد؛ سوري، سوبهاش (1992)، "الانتقالات في الأشجار الممتدة الدنيا الهندسية"، الهندسة المنفصلة والحسابية ، 8 (3): 265-293 ، doi : 10.1007/BF02293049 ، MR 1174358 ، S2CID 30101649

[nzz-8] 1 2 ناراسيمهان، جيري؛ زاكارياسن، مارتن؛ تشو، جيانلين ( 2000)، "تجارب في حساب الأشجار الممتدة الدنيا الهندسية"، وقائع ورشة العمل الثانية حول هندسة الخوارزميات والتجارب ، ص 183-196

[frakau-9] 1 2 فراتي، فابريزيو؛ كوفمان، مايكل (2011)، "حدود مساحة متعددة الحدود لتضمينات MST للأشجار"، الهندسة الحسابية: النظرية والتطبيقات ، 44 (9): 529-543 ، doi : 10.1016/j.comgeo.2011.05.005 ، MR 2819643 ، S2CID 5634139

[king-10] 1 2 كينغ، جيمس أ. (2006)، "تحقيق الأشجار الممتدة الدنيا من الدرجة 10 في الفضاء ثلاثي الأبعاد" (ملف PDF) ، وقائع المؤتمر الكندي السنوي الثامن عشر للهندسة الحسابية، CCCG 2006، 14-16 أغسطس 2006، جامعة كوينز، أونتاريو، كندا ، الصفحات 39-42

[kln-11] 1 2 كرزناريتش، دراغو؛ ليفكوبولوس، كريستوس؛ نيلسون، بينجت ج. (1999)، “الحد الأدنى من الأشجار الممتدة في $d$ الأبعاد"، المجلة الإسكندنافية للحوسبة ، 6 (4): 446-461 ، MR 1736451 هذه النسخة من هذه الورقة غير متاحة عبر الإنترنت؛ بدلاً من ذلك، انظر نسخة المؤتمر لعام 1997 من نفس الورقة، doi : 10.1007/3-540-63397-9_26 .

[gilpol-12] 1 2 3 4 5 6 7 جيلبرت، إي إن ؛ بولاك، إتش أو (1968)، "أشجار شتاينر الدنيا"، مجلة SIAM للرياضيات التطبيقية ، 16 (1): 1-29 ، doi : 10.1137/0116001 ، JSTOR 2099400 ، MR 0223269

[eppstein-13] 1 2 3 4 إبستين، ديفيد (1999)، "الأشجار الممتدة والممتدات" (ملف PDF) ، في ساك، جيه.-آر .؛ أوروتيا، جيه. (محرران)، دليل الهندسة الحسابية ، إلسيفير، الصفحات 425-461 ، MR 1746681

[1steiner-14] جورجاكوبولوس، جورج. Papadimitriou، Christos H. (1987)، “The 1-Steiner Tree مشكلة”، مجلة الخوارزميات ، 8 (1): 122–130 ، دوى : 10.1016 / 0196-6774(87)90032-0 ، MR 0875330

[robsal-15] 1 2 روبنز، جي.؛ سالو، جيه إس (1995)، "الأشجار الممتدة الدنيا منخفضة الدرجة"، الهندسة المنفصلة والحسابية ، 14 (2): 151-165 ، doi : 10.1007/BF02570700 ، MR 1331924 ، S2CID 16040977

[kissing-16] بفندر، فلوريان؛ زيغلر، غونتر م. ( سبتمبر 2004)، "أعداد التقبيل، وتعبئة الكرات، وبعض البراهين غير المتوقعة" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية : 873-883

[sse-17] ستيل، ج. مايكل ؛ شيب، لورانس أ.؛ إيدي، ويليام ف. (1987)، "حول عدد أوراق الشجرة الممتدة الدنيا الإقليدية"، مجلة الاحتمالات التطبيقية ، 24 (4): 809-826 ، doi : 10.2307/3214207 ، JSTOR 3214207 ، MR 0913823 ، S2CID 29026025

[presha-18] بريباراتا، فرانكو ب .؛ شاموس، مايكل إيان (1985)، الهندسة الحسابية: مقدمة ، نصوص ودراسات في علوم الحاسوب، سبرينغر-فيرلاغ، نيويورك، ص 263، doi : 10.1007/978-1-4612-1098-6 ، ISBN 0-387-96131-3، MR 0805539 ، S2CID 206656565

[comment-19] توسان، جي تي (1980)، "تعليق: خوارزميات لحساب الرسم البياني للجوار النسبي"، رسائل الإلكترونيات ، 16 (22): 860، رمز Bibcode : 1980ElL....16..860T ، doi : 10.1049/el:19800611 رد أوركهارت، الصفحات 860-861

[yao82-20] 1 2 3 ياو، أندرو تشي تشيه (1982)، "حول بناء الأشجار الممتدة الدنيا في الفضاءات ذات الأبعاد $k$ والمشاكل ذات الصلة"، مجلة SIAM للحوسبة ، 11 (4): 721-736 ، doi : 10.1137/0211059 ، MR 0677663

[bwy-21] 1 2 بنتلي، جون لويس ؛ وايد، بروس دبليو؛ ياو، أندرو سي (1980)، "خوارزميات الوقت المتوقع الأمثل لمسائل أقرب نقطة" ، معاملات ACM في البرمجيات الرياضية ، 6 (4): 563-580 ، doi : 10.1145/355921.355927 ، MR 0599977 ، S2CID 17238717

[ss89-22] ستيل، ج. مايكل ؛ سنايدر، تيموثي لو (1989)، "معدلات النمو في أسوأ الحالات لبعض المسائل الكلاسيكية في التحسين التوافقي" ، مجلة SIAM للحوسبة ، 18 (2): 278-287 ، doi : 10.1137/0218019 ، MR 0986667

[steele-23] ستيل، ج. مايكل (1988)، "معدلات نمو الأشجار الممتدة الدنيا الإقليدية ذات الحواف الموزونة بالقوة"، حوليات الاحتمالات ، 16 (4): 1767-1787 ، doi : 10.1214/aop/1176991596 ، JSTOR 2243991 ، MR 0958215

[penrose-24] بينروز، ماثيو د. (1997)، "أطول حافة في الشجرة الممتدة الدنيا العشوائية"، حوليات الاحتمالات التطبيقية ، 7 (2): 340-361 ، doi : 10.1214/aoap/1034625335 ، MR 1442317

[bgj78-25] بويس، دبليو إم؛ غاري، إم آر ؛ جونسون، دي إس (1978)، "ملاحظة حول تنصيف الأشجار الممتدة الدنيا"، الشبكات ، 8 (3): 187-192 ، doi : 10.1002/net.3230080302 ، MR 0491324

[bm09-26] 1 2 3 بوتشين، كيفن؛ مولزر، وولفغانغ (2011)، "تثليثات ديلاوناي في زمن $O$ (sort( $n$ )) وأكثر"، مجلة ACM ، 58 (2): A6:1–A6:27، doi : 10.1145/1944345.1944347 ، MR 2786587 ، S2CID 11316974

[mares-27] ماريس، مارتن (2004)، "خوارزميتان خطيتان لإيجاد الشجرة الممتدة الدنيا على فئات الرسوم البيانية المغلقة الصغرى" (ملف PDF) ، أرشيف الرياضيات ، 40 (3): 315-320 ، MR 2107027

[devillers-28] ديفيليرز، أوليفييه (1992)، "التوزيع العشوائي يُنتج خوارزميات بسيطة من رتبة $O$ $($ $n$ $log$ $*$ $n) لمسائل$ $Ω$ $($ $n$ $)$ الصعبة " (ملف PDF) ، المجلة الدولية للهندسة الحسابية والتطبيقات ، 2 (1): 97-111 ، doi : 10.1142/S021819599200007X ، MR 1159844 ، S2CID 60203

[topp-29] أورورك، ج .؛ ديمين، إ. (2001-2002)، "المسألة 5: الشجرة الممتدة الدنيا الإقليدية" ، مشروع المسائل المفتوحة ، كلية سميث

[dwyer-30] دواير، ريكس أ. (1991)، "مخططات فورونوي متعددة الأبعاد في زمن متوقع خطي"، الهندسة المنفصلة والحسابية ، 6 (4): 343-367 ، doi : 10.1007/BF02574694 ، MR 1098813

[kkt-31] كارغر، ديفيد ر.؛ كلاين، فيليب ن.؛ تارجان، روبرت إي. (1995)، "خوارزمية عشوائية خطية لإيجاد الأشجار الممتدة الدنيا"، مجلة ACM ، 42 (2): 321-328 ، doi : 10.1145/201019.201022 ، MR 1409738 ، S2CID 832583

[cck-32] تشاتيرجي، س.؛ كونور، م.؛ كومار، ب. (2010)، "الأشجار الممتدة الدنيا الهندسية باستخدام GeoFilterKruskal"، في فيستا، باولا (محرر)، الخوارزميات التجريبية: الندوة الدولية التاسعة، SEA 2010، جزيرة إيشيا، نابولي، إيطاليا، 20-22 مايو 2010، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 6049، سبرينغر-فيرلاغ، الصفحات 486-500 ، doi : 10.1007/978-3-642-13193-6_41 ، ISBN 978-3-642-13192-9

[arymou-33] آريا، سونيل؛ ماونت، ديفيد م. (2016)، "خوارزمية سريعة وبسيطة لحساب الأشجار الممتدة الدنيا الإقليدية التقريبية"، في كراوثغامر، روبرت (محرر)، وقائع الندوة السنوية السابعة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة، SODA 2016، أرلينغتون، فيرجينيا، الولايات المتحدة الأمريكية، 10-12 يناير 2016، الصفحات 1220-1233 ، doi : 10.1137/1.9781611974331.ch85 ، ISBN 978-1-61197-433-1، MR 3478461

[offline-34] إبستين، ديفيد (1994)، "خوارزميات غير متصلة بالإنترنت لمسائل الشجرة الممتدة الدنيا الديناميكية" ، مجلة الخوارزميات ، 17 (2): 237-250 ، doi : 10.1006/jagm.1994.1033 ، MR 1291541

[chadyn-35] تشان، تيموثي م. (2010)، "بنية بيانات ديناميكية للأغلفة المحدبة ثلاثية الأبعاد واستعلامات أقرب جار ثنائية الأبعاد"، مجلة ACM ، 57 (3): المقالة 16، doi : 10.1145/1706591.1706596 ، MR 2665885 ، S2CID 47454142

[extrema-36] إبستين، ديفيد (1995)، "الأشجار الممتدة الدنيا الإقليدية الديناميكية والقيم القصوى للدوال الثنائية"، الهندسة المنفصلة والحسابية ، 13 (1): 111-122 ، doi : 10.1007/BF02574030 ، MR 1300511 ، S2CID 7339165

[kti-37] كاتوه، ن.؛ توكوياما، ت.؛ إيوانو، ك. (1995)، "حول الأشجار الممتدة الدنيا والقصوى للنقاط المتحركة خطيًا"، الهندسة المنفصلة والحسابية ، 13 (2): 161-176 ، doi : 10.1007/BF02574035 ، MR 1314960

[chalev-38] تشان، تيموثي م. (2003)، "حول المستويات في ترتيبات المنحنيات"، الهندسة المنفصلة والحسابية ، 29 (3): 375-393 ، doi : 10.1007/s00454-002-2840-2 ، MR 1961005 ، S2CID 18966889

[rzcomb-39] رحمتي، زاهد؛ زارعي، علي رضا (2010)، "التغييرات التوافقية للشجرة الممتدة الدنيا الإقليدية للنقاط المتحركة في المستوى" (ملف PDF) ، وقائع المؤتمر الكندي السنوي الثاني والعشرين للهندسة الحسابية، وينيبيغ، مانيتوبا، كندا، 9-11 أغسطس 2010 ، ص 43-45

[abb-40] أكيتيا، هوغو أ.؛ بينياز، أحمد؛ بوس، بروسنجيت ؛ دي كاروفيل، جان لو؛ ماهيشواري، أنيل؛ دا سيلفيرا، لويس فرناندو شولتز خافيير؛ سميد، ميشيل (2021)، "مسألة الشجرة الممتدة المتحركة الدنيا"، في لوبيو، آنا ؛ سالافاتيبور، محمد ر. (محرران)، الخوارزميات وهياكل البيانات: الندوة الدولية السابعة عشرة، WADS 2021، حدث افتراضي، 9-11 أغسطس 2021، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 12808، سبرينغر، الصفحات 15-28 ، doi : 10.1007/978-3-030-83508-8_2 ، ISBN 978-3-030-83507-1، S2CID 234599877

[bgz-41] باش، جوليان؛ غيباس، ليونيداس ج .؛ تشانغ، لي (1997)، "مسائل التقارب على النقاط المتحركة"، في بويسونات، جان-دانيال (محرر)، وقائع الندوة السنوية الثالثة عشرة حول الهندسة الحسابية، نيس، فرنسا، 4-6 يونيو 1997 ، رابطة آلات الحوسبة، ص 344-351 ، doi : 10.1145/262839.262998 ، ISBN 0-89791-878-9، S2CID 15556637

[aegh-42] أغاروال، بانكاج ك .؛ إبستين، ديفيد ؛ غيباس، ليونيداس ج .؛ هينزينغر، مونيكا راوخ (1998)، "الأشجار الممتدة الدنيا البارامترية والحركية"، الندوة السنوية التاسعة والثلاثون حول أسس علوم الحاسوب، FOCS '98، 8-11 نوفمبر 1998، بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية (ملف PDF) ، جمعية IEEE للحاسوب، الصفحات 596-605 ، doi : 10.1109/SFCS.1998.743510 ، ISBN 0-8186-9172-7، S2CID 2559456

[rzkin-43] رحمتي، زاهد؛ زارعي، علي رضا (2012)، "شجرة الامتداد الأدنى الإقليدية الحركية في المستوى"، مجلة الخوارزميات المنفصلة ، 16 : 2-11 ، doi : 10.1016/j.jda.2012.04.009 ، MR 2960341

[rakwz-44] 1 2 رحمتي، زاهد؛ أبام، محمد علي؛ كينغ، فاليري ؛ وايتسايدز، سو ؛ زارعي، علي رضا (2015)، "طريقة بسيطة وأسرع لمسائل التقارب الحركي"، الهندسة الحسابية: النظرية والتطبيقات ، 48 (4): 342-359 ، arXiv : 1311.2032 ، doi : 10.1016/j.comgeo.2014.12.002 ، MR 3296072 ، S2CID 18971251

[msvw-45] ميولمانز، ووتر؛ سبيكمان، بيتينا ؛ فيربيك، كيفن؛ وولمز، جولز (2018)، "إطار عمل لاستقرار الخوارزميات وتطبيقه على أشجار الامتداد الدنيا الإقليدية الحركية"، في بيندر، مايكل أ.؛ فاراش-كولتون، مارتن ؛ موستيرو، ميغيل أ. (محررون)، LATIN 2018: المعلوماتية النظرية - الندوة اللاتينية الأمريكية الثالثة عشرة، بوينس آيرس، الأرجنتين، 16-19 أبريل 2018، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 10807، سبرينغر، الصفحات 805-819 ، doi : 10.1007/978-3-319-77404-6_58 ، ISBN 978-3-319-77403-9، S2CID 4709616

[yao89-46] ياو، أندرو تشي-تشيه (1991)، "الحدود الدنيا لأشجار الحساب الجبري ذات المدخلات الصحيحة"، مجلة SIAM للحوسبة ، 20 (4): 655-668 ، doi : 10.1137/0220041 ، MR 1105929

[history-47] غراهام، آر إل ؛ هيل، بافول (1985)، "حول تاريخ مشكلة الشجرة الممتدة الدنيا"، حوليات IEEE لتاريخ الحوسبة ، 7 (1): 43-57 ، doi : 10.1109/mahc.1985.10011 ، MR 0783327 ، S2CID 10555375

[lobwei-48] لوبرمان، هـ.؛ واينبرغر، أ. (أكتوبر 1957)، "إجراءات رسمية لتوصيل الأطراف بأقل طول إجمالي للسلك"، مجلة ACM ، 4 (4): 428-437 ، doi : 10.1145/320893.320896 ، S2CID 7320964

[urban-49] وو بن. يو، بيلانج؛ وو، تشيوشنغ؛ تشن، زوقي. ياو، شنجون؛ هوانغ، يان. وو، جيان بينغ (أكتوبر 2017)، “طريقة الحد الأدنى الممتد للشجرة الممتدة لتوصيف الأنماط الحضرية المحلية”، المجلة الدولية لعلوم المعلومات الجغرافية ، 32 (3): 450-475 ، دوى : 10.1080/13658816.2017.1384830 ، S2CID 46772272

[zahn-50] زان، سي تي (1973)، "استخدام الشجرة الممتدة الدنيا للتعرف على المنحنيات المنقطة والمتقطعة" ، الندوة الدولية الأولى للحوسبة، دافوس، سويسرا، 4-7 سبتمبر 1973

[lee-51] لي، إن-كوون (2000)، "إعادة بناء المنحنى من نقاط غير منظمة"، التصميم الهندسي بمساعدة الحاسوب ، 17 (2): 161-177 ، CiteSeerX 10.1.1.56.1432 ، doi : 10.1016/S0167-8396(99)00044-8 ، MR 1733203

[bargot-52] بارتال، يائير؛ غوتليب، لي-آد (2013)، "مخطط تقريب زمني خطي لمسألة البائع المتجول الإقليدية"، المؤتمر السنوي الرابع والخمسون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، FOCS 2013، 26-29 أكتوبر 2013، بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية ، الصفحات 698-706 ، CiteSeerX 10.1.1.409.1291 ، doi : 10.1109/FOCS.2013.80 ، ISBN 978-0-7695-5135-7، MR 3246273 ، S2CID 17514182

[wclf-53] وان، ب.-ج.؛ كالينسكو، ج.؛ لي، إكس.-واي.؛ فريدر، أ. (2002)، "البث بأقل طاقة في الشبكات اللاسلكية الثابتة المخصصة"، الشبكات اللاسلكية ، 8 (6): 607-617 ، doi : 10.1023/a:1020381720601 ، S2CID 1297518

[chrvp-54] كليمنتي، أندريا إي إف؛ هويبان، غورفان؛ روسي، جيانلوكا؛ فيرهوفن، يان سي؛ بينا، باولو (2003)، "حول نسبة التقريب للطريقة الاستدلالية القائمة على شجرة الامتداد الأدنى لمشكلة البث الموفر للطاقة في شبكات الراديو الثابتة المخصصة"، المؤتمر الدولي السابع عشر للمعالجة المتوازية والموزعة (IPDPS 2003)، 22-26 أبريل 2003، نيس، فرنسا، وقائع المؤتمر ، جمعية مهندسي الكهرباء والإلكترونيات، ص 222، doi : 10.1109/IPDPS.2003.1213407 ، ISBN 0-7695-1926-1، S2CID 17863487

[fknp-55] فلاميني، ميشيل؛ كلاسينغ، رالف؛ نافارا، ألفريدو؛ بيرينيس، ستيفان (2007)، "نتائج تقريبية محسّنة لمسألة بث الطاقة الدنيا"، Algorithmica ، 49 (4): 318-336 ، doi : 10.1007/s00453-007-9077-7 ، MR 2358524 ، S2CID 11982404

[ambuhl-56] أمبوهل، كريستوف (2005)، "حد أمثل لخوارزمية MST لحساب أشجار البث الموفرة للطاقة في الشبكات اللاسلكية"، في كايريس، لويس؛ إيتاليانو، جوزيبي ف .؛ مونتيرو، لويس؛ بالاميديسي، كاتوسيا ؛ يونغ، موتي (محررون)، الأوتوماتا واللغات والبرمجة، الندوة الدولية الثانية والثلاثون، ICALP 2005، لشبونة، البرتغال، 11-15 يوليو 2005، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 3580، سبرينغر، الصفحات 1139-1150 ، doi : 10.1007/11523468_92 ، ISBN 978-3-540-27580-0

[ew94-57] إيدز، بيتر ؛ وايتسايدز، سو (1996)، "مشكلة تحقيق الأشجار الممتدة الدنيا الإقليدية هي مسألة صعبة من نوع NP"، Algorithmica ، 16 (1): 60-82 ، doi : 10.1007/s004539900037 ، MR 1394494

[abcfks-58] أنجيليني، باتريزيو؛ بروكدورفر، تيل؛ كييزا، ماركو؛ فراتي، فابريزيو؛ كوفمان، مايكل؛ سكوارسيلا، كلاوديو (2014)، "حول متطلبات مساحة الأشجار الممتدة الدنيا الإقليدية"، الهندسة الحسابية: النظرية والتطبيقات ، 47 (2، الجزء ب): 200-213 ، doi : 10.1016/j.comgeo.2012.10.011 ، MR 3123788

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

8 ] وعندما

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

22

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

38

متواليات

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

[

44

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[ 57 ]

[ 58 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗