خوارزمية بنتلي-أوتمان

في الهندسة الحسابية ، تُعد خوارزمية بنتلي-أوتمان خوارزمية مسح خطي لحصر جميع نقاط التقاطع في مجموعة من القطع المستقيمة ، أي أنها تجد نقاط التقاطع (أو ببساطة، نقاط التقاطع ) للقطع المستقيمة. وهي امتداد لخوارزمية شاموس-هوي ، ^{[ 1 ]} وهي خوارزمية سابقة مماثلة لاختبار ما إذا كانت مجموعة من القطع المستقيمة تحتوي على أي نقاط تقاطع أم لا. بالنسبة لمدخل يتكون من${\displaystyle n}$قطع مستقيمة مع${\displaystyle k}$عند التقاطعات (أو نقاط التقاطع)، تستغرق خوارزمية بنتلي-أوتمان وقتًا${\displaystyle {\mathcal {O}}((n+k)\log n)}$في الحالات التي${\displaystyle k={\mathcal {o}}\left({\frac {n^{2}}{\log n}}\right)}$هذا تحسين على خوارزمية بسيطة تختبر كل زوج من القطع، والتي تأخذ${\displaystyle \Theta (n^{2})}$.

طُوِّرت الخوارزمية في البداية على يد جون بنتلي وتوماس أوتمان ( 1979 ) ؛ ووُصِفت بمزيد من التفصيل في الكتب الدراسية لبريباراتا وشاموس (1985) ، وأورورك (1998) ، ودي بيرغ وآخرون (2000) . على الرغم من وجود خوارزميات أسرع تقاربياً معروفة الآن من قِبَل شازيل وإيدلسبرونر (1992) وبالابان (1995) ، إلا أن خوارزمية بنتلي-أوتمان لا تزال خياراً عملياً نظراً لبساطتها وانخفاض متطلبات الذاكرة . 

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

1. لا يوجد نقطتا نهاية أو تقاطع لقطعتين مستقيمتين لهما نفس الإحداثي السيني
2. لا تقع أي نقطة نهاية لقطعة مستقيمة على قطعة مستقيمة أخرى
3. لا تتقاطع ثلاثة قطع مستقيمة في نقطة واحدة.

في هذه الحالة، سيتقاطع الخط L دائمًا مع القطع المستقيمة المدخلة في مجموعة من النقاط التي يتغير ترتيبها الرأسي فقط عند مجموعة محدودة من الأحداث المنفصلة . تحديدًا، يمكن ربط الحدث المنفصل إما بنقطة نهاية (يسار أو يمين) لقطعة مستقيمة أو بنقطة تقاطع قطعتين مستقيمتين. وبالتالي، يمكن تقسيم الحركة المستمرة للخط L إلى سلسلة محدودة من الخطوات، ومحاكاتها بواسطة خوارزمية تعمل في فترة زمنية محدودة.

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

تحتفظ خوارزمية بنتلي-أوتمان بهياكل بيانات تمثل الترتيب الرأسي الحالي لنقاط تقاطع خط المسح مع أجزاء خط الإدخال، ومجموعة من الأحداث المستقبلية المحتملة التي تشكلها أزواج نقاط التقاطع المتجاورة. وتعالج كل حدث بدوره، محدثةً هياكل بياناته لتمثيل المجموعة الجديدة من نقاط التقاطع.

من أجل الحفاظ بكفاءة على نقاط تقاطع خط المسح L مع أجزاء خط الإدخال وتسلسل الأحداث المستقبلية، تحتفظ خوارزمية بنتلي-أوتمان ببنيتين من البيانات :

• شجرة بحث ثنائية (تُسمى "شجرة حالة خط المسح")، تحتوي على مجموعة من قطع الخطوط المدخلة التي تتقاطع مع الخط L ، مرتبة حسب إحداثيات y لنقاط تقاطع هذه القطع مع L. لا تُمثَّل نقاط التقاطع نفسها بشكل صريح في شجرة البحث الثنائية. تُدرج خوارزمية بنتلي-أوتمان قطعة جديدة s في بنية البيانات هذه عندما يتقاطع خط المسح L مع نقطة النهاية اليسرى p لهذه القطعة (أي نقطة نهاية القطعة ذات أصغر إحداثي x ، بشرط أن يبدأ خط المسح L من اليسار، كما هو موضح أعلاه في هذه المقالة). يمكن تحديد الموضع الصحيح للقطعة s في شجرة البحث الثنائية من خلال بحث ثنائي، حيث تختبر كل خطوة ما إذا كانت p أعلى أو أسفل قطعة أخرى يتقاطع معها L. وبالتالي، يمكن إجراء عملية الإدراج في وقت لوغاريتمي. كما تحذف خوارزمية بنتلي-أوتمان القطع من شجرة البحث الثنائية، وتستخدم شجرة البحث الثنائية لتحديد القطع التي تقع مباشرة فوق أو أسفل قطع أخرى. يمكن تنفيذ هذه العمليات باستخدام بنية الشجرة نفسها فقط دون الرجوع إلى الهندسة الأساسية للقطاعات.

• تُستخدم قائمة انتظار ذات أولوية (قائمة انتظار الأحداث) في خوارزمية بنتلي-أوتمان للحفاظ على تسلسل الأحداث المستقبلية المحتملة. يرتبط كل حدث بنقطة p في المستوى، إما نقطة نهاية قطعة مستقيمة أو نقطة تقاطع، ويحدث الحدث عندما يمر الخط L فوق النقطة p . وبالتالي، يمكن ترتيب الأحداث حسب الأولوية بناءً على الإحداثيات السينية للنقاط المرتبطة بكل حدث. في خوارزمية بنتلي-أوتمان، تتكون الأحداث المستقبلية المحتملة من نقاط نهاية القطع المستقيمة التي لم يمر بها الخط بعد، ونقاط تقاطع أزواج الخطوط التي تحتوي على أزواج من القطع المستقيمة المتجاورة.

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

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

تقوم خوارزمية بنتلي-أوتمان بالخطوات التالية.

1. أنشئ قائمة انتظار ذات أولوية Q للأحداث المستقبلية المحتملة، حيث يرتبط كل حدث بنقطة في المستوى ويتم ترتيب أولوياتها بناءً على الإحداثي السيني لتلك النقطة. لذا، تحتوي Q مبدئيًا على حدث لكل نقطة من نقاط نهاية أجزاء الإدخال.
2. قم بإنشاء شجرة بحث ثنائية متوازنة ذاتيًا T لقطع الخطوط التي تتقاطع مع خط المسح L ، مرتبة حسب إحداثيات y لنقاط التقاطع. في البداية، تكون T فارغة. (على الرغم من أن خط المسح L غير ممثل بشكل صريح، فقد يكون من المفيد تخيله كخط رأسي يقع في البداية على يسار جميع قطع الإدخال).
3. طالما أن المصفوفة Q غير فارغة، ابحث عن الحدث المرتبط بالنقطة p ذات الإحداثي السيني الأدنى، ثم احذفه من Q. حدد نوع هذا الحدث، ثم عالجه وفقًا لتحليل الحالة التالي:
   • إذا كانت النقطة p هي الطرف الأيسر لقطعة مستقيمة s ، فأدرج s في T. ابحث عن القطعتين المستقيمتين r و t اللتين تقعان مباشرةً فوق s وتحتها في T (إن وُجدتا)؛ إذا كان تقاطع r و t (القطعتين المجاورتين لـ s في بنية بيانات الحالة) يُشكّل حدثًا مستقبليًا محتملاً في قائمة الأحداث، فاحذف هذا الحدث المستقبلي المحتمل من قائمة الأحداث. إذا تقاطع s مع r أو t ، فأضف نقاط التقاطع هذه كأحداث مستقبلية محتملة في قائمة الأحداث.
   • إذا كانت النقطة p هي الطرف الأيمن لقطعة مستقيمة s ، فاحذف s من T. ثم ابحث عن القطعتين r و t اللتين كانتا (قبل حذف s ) أعلى وأسفل القطعة المستقيمة s مباشرةً في T (إن وُجدتا). إذا تقاطعت القطعتان r و t ، فأضف نقطة التقاطع هذه كحدث مستقبلي محتمل في قائمة الأحداث.
   • إذا كانت النقطة p هي نقطة تقاطع قطعتين مستقيمتين s و t (حيث تقع s أسفل t إلى يسار نقطة التقاطع)، فقم بتبديل موضعي s و t في T. بعد التبديل، ابحث عن القطعتين المستقيمتين r و u (إن وُجدتا) اللتين تقعان أسفل t و s مباشرةً وفوقهما مباشرةً، على التوالي. احذف أي نقطتي تقاطع rs (أي نقطة تقاطع بين r و s ) و tu (أي نقطة تقاطع بين t و u ) من قائمة الأحداث، وإذا تقاطعت r و t أو s و u ، فأضف نقطتي التقاطع هاتين إلى قائمة الأحداث.

تقوم الخوارزمية بمعالجة حدث واحد لكل نقطة نهاية مقطع أو نقطة تقاطع، بالترتيب المصنف لـ${\displaystyle x}$إحداثيات هذه النقاط، كما يمكن إثباته بالاستقراء. ويترتب على ذلك أنه بمجرد${\displaystyle i}$بعد معالجة الحدث رقم 1، يجب أن يكون الحدث التالي (إذا كان نقطة تقاطع) تقاطعًا لقطعتين متجاورتين في ترتيب القطع الممثلة بواسطة${\displaystyle T}$ولأن الخوارزمية تحتفظ بجميع نقاط التقاطع بين القطع المستقيمة المتجاورة كأحداث مستقبلية محتملة في قائمة الأحداث، فإن الحدث التالي الصحيح سيكون موجودًا دائمًا في هذه القائمة. ونتيجة لذلك، تجد الخوارزمية جميع نقاط تقاطع القطع المستقيمة المدخلة بدقة، وهي المشكلة التي صُممت لحلها.

تقوم خوارزمية بنتلي-أوتمان بمعالجة سلسلة من${\displaystyle 2n+k}$الأحداث، حيث${\displaystyle n}$يشير إلى عدد أجزاء خط الإدخال و${\displaystyle k}$يشير إلى عدد التقاطعات. تتم معالجة كل حدث بعدد ثابت من العمليات في شجرة البحث الثنائية وقائمة انتظار الأحداث، ونظرًا لأنها لا تحتوي إلا على نقاط نهاية القطاعات والتقاطعات بين القطاعات المتجاورة، فإن قائمة انتظار الأحداث لا تحتوي أبدًا على أكثر من${\displaystyle 3n}$الأحداث. جميع العمليات تستغرق وقتاً.${\displaystyle {\mathcal {O}}(\log n)}$وبالتالي فإن إجمالي وقت تنفيذ الخوارزمية هو${\displaystyle {\mathcal {O}}((n+k)\log n)}$.

إذا لم تكن هناك حاجة لتخزين التقاطعات التي عثرت عليها الخوارزمية بمجرد العثور عليها، فإن المساحة التي تستخدمها الخوارزمية في أي وقت هي${\displaystyle {\mathcal {O}}(n)}$كل واحد من${\displaystyle n}$تتوافق مقاطع خط الإدخال مع عقدة واحدة على الأكثر من شجرة البحث الثنائية T ، وكما ذكر أعلاه، يحتوي طابور الأحداث على الأكثر${\displaystyle 3n}$العناصر. يعود هذا الحد المكاني إلى براون (1981) ؛ وكانت النسخة الأصلية من الخوارزمية مختلفة قليلاً (لم تقم بإزالة أحداث التقاطع من${\displaystyle Q}$عندما يتسبب حدث آخر في عدم تجاور القطعتين المتقاطعتين، مما يؤدي إلى استخدام مساحة أكبر. ^{[ 3 ]}

وصف تشين وتشان (2003) نسخةً عالية الكفاءة من خوارزمية بنتلي-أوتمان، والتي تشفر معظم معلوماتها في ترتيب المقاطع في مصفوفة تمثل المدخلات، ولا تتطلب سوى${\displaystyle {\mathcal {O}}(\log ^{2}n)}$خلايا ذاكرة إضافية. ومع ذلك، من أجل الوصول إلى المعلومات المشفرة، يتم إبطاء الخوارزمية بمعامل لوغاريتمي.

يفترض وصف الخوارزمية أعلاه أن القطع المستقيمة ليست عمودية، وأن نقاط نهاية القطع المستقيمة لا تقع على قطع مستقيمة أخرى، وأن التقاطعات تتكون من قطعتين مستقيمتين فقط، وأنه لا توجد نقطتان لهما نفس الإحداثي السيني . بعبارة أخرى، لا تأخذ الخوارزمية في الحسبان الحالات الشاذة، أي أنها تفترض موقعًا عامًا لنقاط نهاية القطع المستقيمة المدخلة. مع ذلك، فإن افتراضات الموقع العام هذه غير منطقية لمعظم تطبيقات تقاطع القطع المستقيمة. اقترح بنتلي وأوتمان (1979) إجراء تعديل طفيف على المدخلات لتجنب هذه الأنواع من التطابقات العددية، لكنهما لم يصفا بالتفصيل كيفية إجراء هذه التعديلات. يصف دي بيرغ وآخرون (2000) بمزيد من التفصيل التدابير التالية للتعامل مع المدخلات ذات المواقع الخاصة:

• لحلّ حالات التعادل بين نقاط الأحداث ذات الإحداثي السيني نفسه، استخدم الإحداثي الصادي . أما الأحداث ذات الإحداثيات الصادية المختلفة ، فتُعالج كما في السابق. يُعالج هذا التعديل مشكلة وجود نقاط أحداث متعددة ذات إحداثي سيني متطابق، بالإضافة إلى مشكلة القطع المستقيمة الرأسية: حيث تُعرّف نقطة النهاية اليسرى للقطعة المستقيمة الرأسية بأنها تلك ذات الإحداثي الصادي الأقل ، وتكون الخطوات اللازمة لمعالجة هذه القطعة مماثلة لتلك اللازمة لمعالجة قطعة مستقيمة غير رأسية ذات ميل شديد.
• يُعرَّف الخط المستقيم بأنه مجموعة مغلقة تحتوي على نقطتي نهايته. لذلك، يُعتبر كل من الخطين المستقيمين اللذين يشتركان في نقطة نهاية واحدة، أو الخط المستقيم الذي يحتوي على نقطة نهاية خط مستقيم آخر، تقاطعًا لخطين مستقيمين.
• عند تقاطع عدة قطع مستقيمة في نفس النقطة، يتم إنشاء نقطة حدث واحدة ومعالجتها. قد تتضمن التحديثات التي تُجرى على شجرة البحث الثنائية نتيجةً لهذا الحدث إزالة أي قطع مستقيمة تُمثل هذه النقطة نهايتها اليمنى، وإضافة قطع مستقيمة جديدة تُمثل هذه النقطة نهايتها اليسرى، وعكس ترتيب القطع المستقيمة المتبقية التي تحتوي على نقطة الحدث هذه. يتكون ناتج نسخة الخوارزمية الموصوفة من قِبل دي بيرغ وآخرون (2000) من مجموعة نقاط تقاطع القطع المستقيمة، مُصنفةً حسب القطع التي تنتمي إليها، بدلاً من مجموعة أزواج القطع المستقيمة المتقاطعة.

تم استخدام نهج مماثل للتعامل مع حالات الانحلال في تطبيق خوارزمية بنتلي-أوتمان في برنامج LEDA . ^{[ 4 ]}

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

يُعدّ الجزء O( n log n ) من الحد الزمني لخوارزمية بنتلي-أوتمان ضروريًا، نظرًا لوجود حدود دنيا مماثلة لمشكلة اكتشاف تقاطع القطع المستقيمة في نماذج شجرة القرار الجبرية للحساب. ^{[ 5 ]} ومع ذلك، يمكن تحسين الاعتماد على k ، أي عدد التقاطعات. قدّم كلٌّ من كلاركسون (1988) ومولمولي (1988) خوارزميات عشوائية لإنشاء الرسم البياني المستوي الذي تمثل رؤوسه نقاط نهاية وتقاطعات القطع المستقيمة، وتمثل حوافه أجزاء القطع التي تربط هذه الرؤوس، في زمن متوقع O( n log n + k ). وقد حُلّت مشكلة إنشاء هذا الترتيب بشكل حتمي في نفس الحد الزمني O( n log n + k ) بواسطة شازيل وإيدلسبرونر (1992) . مع ذلك، يتطلب إنشاء هذا الترتيب ككل مساحة O( n + k )، وهي أكبر من حد المساحة O( n ) لخوارزمية بنتلي-أوتمان. وصف بالابان (1995) خوارزمية مختلفة تسرد جميع التقاطعات في الوقت O( n log n + k ) والمساحة O( n ).

إذا كانت قطع الخطوط المدخلة ونهاياتها تُشكّل حواف ورؤوس رسم بياني متصل (مع احتمال وجود تقاطعات)، فإنه يُمكن تقليل الجزء O( n log n ) من الحد الزمني لخوارزمية بنتلي-أوتمان. وكما بيّن كلاركسون وكول وتارجان (1992) ، توجد في هذه الحالة خوارزمية عشوائية لحل المشكلة في زمن متوقع O( n log* n + k )، حيث يرمز log * إلى اللوغاريتم المُكرّر ، وهي دالة تنمو ببطء أكبر بكثير من اللوغاريتم. وتحل خوارزمية عشوائية وثيقة الصلة من إبستين وجودريتش وستراش (2009) المشكلة نفسها في زمن O( n + k log ^{( i )} n ) لأي ثابت i ، حيث يرمز log ^{( i )} إلى الدالة الناتجة عن تكرار دالة اللوغاريتم i مرة. تستغرق الخوارزمية الأولى زمنًا خطيًا عندما تكون قيمة k أكبر من n بمعامل log ^{( i )} n ، لأي قيمة ثابتة i ، بينما تستغرق الخوارزمية الثانية زمنًا خطيًا عندما تكون قيمة k أصغر من n بمعامل log ^{( i )} n . وتتضمن كلتا الخوارزميتين تطبيق خوارزمية بنتلي-أوتمان على عينات عشوائية صغيرة من المدخلات.

• بالابان، آي جيه (1995)، "خوارزمية مثلى لإيجاد تقاطعات القطع المستقيمة"، وقائع الندوة الحادية عشرة لجمعية الحوسبة الآلية حول الهندسة الحسابية ، الصفحات 211-219 ، doi : 10.1145/220279.220302 ، ISBN  0-89791-724-3، S2CID 6342118 .
• بارتوشكا، يو.؛ ميلهورن، ك .؛ ناهر، س. (1997)، "تنفيذ قوي وفعال لخوارزمية خط المسح لمسألة تقاطع القطع المستقيمة" ، باللغة الإيطالية، جي إف ؛ أورلاندو، س. (محرران)، وقائع ورشة عمل هندسة الخوارزميات ، مؤرشفة من الأصل في 2017-06-06 ، تم استرجاعها في 2009-05-27.
• بنتلي، جيه إل ؛ أوتمان، تي إيه (1979)، "خوارزميات للإبلاغ عن التقاطعات الهندسية وحسابها"، معاملات IEEE للحواسيب ، C-28 (9): 643-647 ، doi : 10.1109/TC.1979.1675432 ، S2CID 1618521 .
• دي بيرج، مارك؛ فان كريفيلد، مارك؛ أوفرمارس, مارك ; Schwarzkopf، Otfried (2000)، “الفصل 2: ​​تقاطع مقطع الخط” ، الهندسة الحسابية (  الطبعة الثانية)، Springer-Verlag، الصفحات من 19 إلى 44 ، ISBN  978-3-540-65620-3.
• بويسونات، جيه-دي؛ بريباراتا، إف بي (2000)، "مسح مستوي قوي للقطاعات المتقاطعة" (ملف PDF) ، مجلة SIAM للحوسبة ، 29 (5): 1401-1421 ، doi : 10.1137/S0097539797329373.
• براون، كيو كيو (1981)، "تعليقات على "خوارزميات الإبلاغ عن التقاطعات الهندسية وحسابها"، IEEE Transactions on Computers ، C-30 (2): 147، doi : 10.1109/tc.1981.6312179 ، S2CID 206622367 .
• شازيل، برنارد ؛ إيدلسبرونر، هربرت (1992)، "خوارزمية مثلى لتقاطع القطع المستقيمة في المستوى"، مجلة ACM ، 39 (1): 1-54 ، doi : 10.1145/147508.147511 ، S2CID 785741 .
• تشين، إي واي؛ تشان، تي إم (2003)، "خوارزمية فعالة من حيث المساحة لتقاطع القطع المستقيمة"، وقائع المؤتمر الكندي الخامس عشر للهندسة الحسابية (PDF).
• كلاركسون، ك. ل. (1988)، "تطبيقات أخذ العينات العشوائية في الهندسة الحسابية، الجزء الثاني"، وقائع الندوة الرابعة لجمعية آلات الحوسبة حول الهندسة الحسابية ، الصفحات 1-11 ، doi : 10.1145/73393.73394 ، ISBN  0-89791-270-5، S2CID 15134654 .
• كلاركسون، ك. ل .؛ كول، ر.؛ تارجان، ر. إ. (1992)، "خوارزميات متوازية عشوائية للرسوم البيانية شبه المنحرفة"، المجلة الدولية للهندسة الحسابية والتطبيقات ، 2 (2): 117-133 ، doi : 10.1142/S0218195992000081. تصويب، 2 (3): 341-343.
• إبستين، د .؛ غودريتش، م .؛ ستراش، د. (2009)، "خوارزميات خطية الزمن للرسوم البيانية الهندسية ذات عدد التقاطعات شبه الخطي"، وقائع الندوة العشرين لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة (SODA 2009) ، الصفحات 150-159 ، arXiv : 0812.0893 ، Bibcode : 2008arXiv0812.0893E ، ​​doi : 10.1137/090759112 ، S2CID 13044724  .
• مولمولي، ك. (1988)، "خوارزمية تقسيم مستوية سريعة، الجزء الأول"، وقائع الندوة التاسعة والعشرين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS 1988) ، الصفحات 580-589 ، doi : 10.1109/SFCS.1988.21974 ، ISBN  0-8186-0877-3، S2CID 34582594 .
• أورورك، ج. (1998)، "القسم 7.7: تقاطع القطع المستقيمة"، الهندسة الحسابية بلغة سي (  الطبعة الثانية)، مطبعة جامعة كامبريدج، الصفحات 263-265 ، رقم ISBN  978-0-521-64976-6.
• بريباراتا، إف بي ؛ شاموس، إم آي (1985)، "القسم 7.2.3: تقاطع القطع المستقيمة"، الهندسة الحسابية: مقدمة ، سبرينغر-فيرلاغ، ص 278-287 ، رمز Bibcode : 1985cgai.book.....P .
• باتش، ج .؛ شارير، م. (1991)، "حول الرؤية الرأسية في ترتيبات القطع وحجم قائمة الانتظار في خوارزمية بنتلي-أوتمان لمسح الخطوط"، مجلة SIAM للحوسبة ، 20 (3): 460-470 ، doi : 10.1137/0220029 ، MR 1094525 .
• شاموس، إم آي ؛ هوي، دان (1976)، "مسائل التقاطع الهندسي"، المؤتمر السابع عشر لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS 1976) ، الصفحات 208-215 ، doi : 10.1109/SFCS.1976.16 ، S2CID 124804  .

• سميد، ميشيل (2003)، حساب التقاطعات في مجموعة من القطع المستقيمة: خوارزمية بنتلي-أوتمان (PDF).