موقع النقطة

اكتشف دوبكين وليبتون في عام 1976 أبسط وأقدم بنية بيانات تحقق زمنًا قدره O(log n ) . تعتمد هذه البنية على تقسيم S باستخدام خطوط رأسية تمر عبر كل رأس في S. تُسمى المنطقة بين خطين رأسيين متتاليين " شريحة" . لاحظ أن كل شريحة مقسمة بقطع مستقيمة غير متقاطعة تعبر الشريحة بالكامل من اليسار إلى اليمين. المنطقة بين قطعتين مستقيمتين متتاليتين داخل الشريحة تُقابل وجهًا فريدًا من S. لذلك، نُبسط مسألة تحديد موقع النقاط إلى مسألتين أبسط: ^{[ 2 ]}

1. بالنظر إلى تقسيم المستوى إلى ألواح رأسية، حدد أي لوح يحتوي على نقطة معينة.
2. بالنظر إلى لوح مقسم إلى مناطق بواسطة أجزاء غير متقاطعة تعبر اللوح بالكامل من اليسار إلى اليمين، حدد المنطقة التي تحتوي على نقطة معينة.

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

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

السلسلة الرتيبة (الرأسية) هي مسار لا يزيد فيه الإحداثي y على طول المسار. يكون المضلع البسيط رتيبًا (رأسيًا) إذا كان مكونًا من سلسلتين رتيبتين، تشتركان في الرأسين الأول والأخير. من الممكن إضافة بعض الحواف إلى تقسيم مستوٍ لجعل جميع الأوجه رتيبة، فنحصل على ما يُسمى بالتقسيم الرتيب. لا تُضيف هذه العملية أي رؤوس إلى التقسيم (وبالتالي، يبقى الحجم O( n ))، ويمكن تنفيذها في زمن O( n log n ) باستخدام مسح المستوى (كما يمكن تنفيذها في زمن خطي باستخدام تثليث المضلع ). لذلك، لا يوجد فقدان للعمومية إذا قصرنا بنية بياناتنا على حالة التقسيمات الرتيبة، كما نفعل في هذا القسم.

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

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

تفاصيل حل المشكلتين الأوليين تتجاوز نطاق هذه المقالة. سنشير بإيجاز إلى كيفية معالجة المشكلة الثالثة. باستخدام البحث الثنائي، يمكننا اختبار ما إذا كانت نقطة ما تقع على يسار أو يمين سلسلة رتيبة في زمن قدره O(log n ). ولأننا نحتاج إلى إجراء بحث ثنائي متداخل آخر عبر O(log n ) سلسلة لتحديد موقع النقطة بدقة، فإن زمن الاستعلام هو O(log² n). ولتحقيق زمن استعلام قدره O(log n )، نحتاج إلى استخدام التتالي الجزئي ، مع الاحتفاظ بالمؤشرات بين حواف السلاسل الرتيبة المختلفة. ^{[ 4 ]}

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

تتلخص الفكرة العامة في بناء تسلسل هرمي من المثلثات. لإجراء استعلام، نبدأ بإيجاد المثلث الأعلى الذي يحتوي على نقطة الاستعلام. وبما أن عدد المثلثات الأعلى محدود بثابت، يمكن تنفيذ هذه العملية في زمن ثابت O(1). يحتوي كل مثلث على مؤشرات إلى المثلثات التي يتقاطع معها في المستوى التالي من التسلسل الهرمي، وعدد هذه المؤشرات محدود أيضًا بثابت. نتابع الاستعلام بإيجاد المثلث الذي يحتوي على نقطة الاستعلام مستوىً تلو الآخر. ^{[ 5 ]}

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

يعتمد أحد الأساليب العشوائية لحل هذه المشكلة على التقسيم شبه المنحرف ، أو الخريطة شبه المنحرفة. يُحصل على التقسيم شبه المنحرف بإطلاق رصاصات عمودية لأعلى ولأسفل من كل رأس في التقسيم الأصلي. تتوقف الرصاصات عند اصطدامها بحافة، لتشكل حافة جديدة في التقسيم. بهذه الطريقة، نحصل على مجموعة فرعية من تقسيم الشريحة، تحتوي على O( n ) فقط من الحواف والرؤوس، حيث نضيف لكل رأس في التقسيم الأصلي رأسين جديدين فقط، ونزيد عدد الحواف بمقدار أربعة. ^{[ 6 ]}

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

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