مخطط الطاقة

الموسوعة الحرة
مخطط قوة لأربع دوائر

في الهندسة الحسابية ، يُعرف مخطط القوة ، أو مخطط لاغير-فورونوي ، أو مُركّب خلايا ديريشليه ، أو تجزئة فورونوي الجذرية ، أو تجزئة ديريشليه القطاعية ، بأنه تقسيم للمستوى الإقليدي إلى خلايا مضلعة مُحددة من مجموعة دوائر. تتكون خلية دائرة معينة C من جميع النقاط التي تكون فيها مسافة القوة إلى C أصغر من مسافة القوة إلى الدوائر الأخرى. يُعد مخطط القوة شكلاً من أشكال مخطط فورونوي المُعمم ، ويتطابق مع مخطط فورونوي لمراكز الدوائر في حالة تساوي أنصاف أقطار جميع الدوائر. [ 1 ] [ 2 ] [ 3 ] [ 4 ]

تعريف

قوة النقطة P خارج دائرة معينة

إذا كانت C دائرة و P نقطة خارجها ، فإن قوة P بالنسبة إلى C تساوي مربع طول قطعة مستقيمة من P إلى نقطة T مماسة لـ C. وبصورة مكافئة، إذا كانت المسافة بين P ومركز الدائرة d ، ونصف قطر الدائرة r ، فإن القوة (بحسب نظرية فيثاغورس) تساوي d² - r² . ويمكن تعميم الصيغة نفسها d² - r² على جميع النقاط في المستوى، سواء كانت داخل C أو خارجها : النقاط الواقعة على C قوتها صفر، والنقاط الواقعة داخل C قوتها سالبة . [ 2 ] [ 3 ] [ 4 ]    

مخطط القوة لمجموعة من n دائرة C i هو تقسيم للمستوى إلى n منطقة R i (تسمى خلايا)، بحيث تنتمي النقطة P إلى R i كلما كانت الدائرة C i هي الدائرة التي تقلل من قوة P. [ 2 ] [ 3 ] [ 4 ]

المحور الجذري لدائرتين متقاطعتين. مخطط القوة للدائرتين هو تقسيم المستوى إلى نصفين مستويين يشكلهما هذا الخط.

في حالة n  =  2، يتكون مخطط القوة من نصفَي مستوى ، يفصل بينهما خط يُسمى المحور الجذري أو وتر الدائرتين. على طول المحور الجذري، تتساوى قوة الدائرتين. وبشكل أعم، في أي مخطط قوة، تكون كل خلية Ri مضلعًا محدبًا ، وهو تقاطع نصفَي الفضاء المحصورين بالمحاور الجذرية للدائرة Ri مع كل دائرة أخرى. تلتقي ثلاثيات الخلايا عند رؤوس المخطط، وهي المراكز الجذرية للدوائر الثلاث التي تلتقي خلاياها عند الرأس . [ 2 ] [ 3 ] [ 4 ]

يمكن اعتبار مخطط القوة شكلاً مُرجَّحًا لمخطط فورونوي لمجموعة من المواقع النقطية، وهو تقسيم للمستوى إلى خلايا يكون فيها أحد المواقع أقرب من جميع المواقع الأخرى. تشمل الأشكال الأخرى لمخطط فورونوي المرجَّح مخطط فورونوي المرجَّح جمعيًا، حيث يُضاف وزن لكل موقع إلى بُعده قبل مقارنته بالمسافات إلى المواقع الأخرى، ومخطط فورونوي المرجَّح ضربيًا، حيث يُضرب وزن الموقع في بُعده قبل مقارنته بالمسافات إلى المواقع الأخرى. في المقابل، في مخطط القوة، يمكننا اعتبار مركز كل دائرة موقعًا، ومربع نصف قطر كل دائرة وزنًا يُطرح من مربع المسافة الإقليدية قبل مقارنته بمربعات المسافات الأخرى. في حالة تساوي جميع أنصاف أقطار الدوائر، لا يُحدث هذا الطرح أي فرق في المقارنة، ويتطابق مخطط القوة مع مخطط فورونوي. [ 3 ] [ 4 ]

يمكن أيضًا تفسير مخطط القدرة المستوي على أنه مقطع عرضي مستوٍ لمخطط فورونوي ثلاثي الأبعاد غير مُرجَّح. في هذا التفسير، تمثل مجموعة مراكز الدوائر في مستوى المقطع العرضي الإسقاطات العمودية لمواقع فورونوي ثلاثية الأبعاد، ويكون مربع نصف قطر كل دائرة ثابتًا K مطروحًا منه مربع المسافة بين الموقع المقابل ومستوى المقطع العرضي، حيث يتم اختيار قيمة K كبيرة بما يكفي لجعل جميع أنصاف الأقطار موجبة. [ 5 ]

على غرار مخطط فورونوي، يمكن تعميم مخطط القوة ليشمل الفضاءات الإقليدية ذات أي بُعد. مخطط القوة لـ n كرة في d بُعد مكافئ توافقيًا لتقاطع مجموعة من n نصف فضاء متجهة للأعلى في d  +  1 بُعد، والعكس صحيح. [ 3 ]

الخوارزميات والتطبيقات

يمكن إنشاء مخططات القدرة ثنائية الأبعاد بواسطة خوارزمية تعمل في زمن O( n  log n ). [ 2 ] [ 3 ] وبشكل أعم، نظرًا لتكافؤها مع تقاطعات نصف الفضاء ذات الأبعاد الأعلى، يمكن إنشاء مخططات القدرة ذات البعد d (لـ d > 2) بواسطة خوارزمية تعمل في زمن   يا(ن⌈د/2⌉){\displaystyle O(n^{\lceil d/2\rceil })}[ 3 ]​

يمكن استخدام مخطط القوة كجزء من خوارزمية فعالة لحساب حجم اتحاد الكرات. يُعطي تقاطع كل كرة مع خلية مخطط القوة الخاصة بها مساهمتها في الاتحاد الكلي، ومن ثم يمكن حساب الحجم في وقت يتناسب مع تعقيد مخطط القوة. [ 6 ]

تشمل التطبيقات الأخرى لمخططات الطاقة هياكل البيانات لاختبار ما إذا كانت نقطة ما تنتمي إلى اتحاد أقراص، [ 2 ] وخوارزميات لإنشاء حدود اتحاد أقراص، [ 2 ] وخوارزميات لإيجاد أقرب كرتين في مجموعة من الكرات. [ 7 ] كما تُستخدم لحل مسألة النقل الأمثل شبه المنفصلة [ 8 ] والتي بدورها لها تطبيقات عديدة، مثل إعادة بناء الكون المبكر [ 9 ] أو ديناميكيات الموائع . [ 10 ]

تاريخ

ينسب أورينهامر (1987) تعريف مسافة القوة إلى أعمال عالمي الرياضيات إدموند لاغير وجورجي فورونوي في القرن التاسع عشر . [ 3 ] عرّف فيجيس توث (1977) مخططات القوة واستخدمها لإثبات أن حدود اتحاد n قرصًا دائريًا يمكن إضاءتها دائمًا من 2n مصدرًا ضوئيًا نقطيًا على الأكثر . [ 11 ] ظهرت مخططات القوة في الأدبيات تحت مسميات أخرى، منها "مخطط لاغير-فورونوي"، و"مركب خلية ديريشليه"، و"تبليط فورونوي الجذري"، و"تبليط ديريشليه القطاعي". [ 12 ]

مراجع

  1. ^ Linhart، J. (1981)، “Dirichletsche Zellenkomplexe mitmaximaler Eckenzahl”، Geometriae Dedicata ، 11 (3): 363–367 ، دوى : 10.1007 / BF00149360 ، السيد 0627538 ، S2CID 120072781  .
  2. 1 2 3 4 5 6 7 إيماي، هيروشي؛ إيري، ماساو؛ موروتو، كازو (1985)، "مخطط فورونوي في هندسة لاغير وتطبيقاته"، مجلة SIAM للحوسبة ، 14 (1): 93-105 ، doi : 10.1137/0214006 ، MR 0774929 .
  3. 1 2 3 4 5 6 7 8 9 أورينهامر، ف. (1987)، "مخططات القدرة: الخصائص والخوارزميات والتطبيقات"، مجلة SIAM للحوسبة ، 16 (1): 78-96 ، doi : 10.1137/0216006 ، MR 0873251 .
  4. 1 2 3 4 5 إيدلسبرونر، هربرت ( 1987)، "13.6 مخططات القوى"، الخوارزميات في الهندسة التوافقية ، سلسلة دراسات EATCS في علوم الحاسوب النظرية، المجلد 10، سبرينغر-فيرلاغ، الصفحات 327-328  .
  5. ^ الرماد، بيتر ف. بولكر، إيثان د. (1986)، “الفسيفساء المعممة لديريشليت”، Geometriae Dedicata ، 20 (2): 209–243 ، دوى : 10.1007 / BF00164401 ، MR 0833848 ، S2CID 120383767  .
  6. ↑ أفيس، ديفيد ؛ بهاتاشاريا، بيناي ك.؛ إيماي، هيروشي (1988)، "حساب حجم اتحاد الكرات" (ملف PDF) ، الحاسوب المرئي ، 3 (6): 323-328 ، doi : 10.1007/BF01901190.
  7. ↑ غيباس، ليونيداس ؛ تشانغ، لي (1998)، "التقارب الإقليدي ومخططات القوة"، المؤتمر الكندي العاشر للهندسة الحسابية.
  8. ↑ أورينهامر، ف.؛ هوفمان، ف.؛ أرونوف، ب. (يناير 1998). "نظريات من نوع مينكوفسكي والتجميع باستخدام طريقة المربعات الصغرى" . Algorithmica . 20 (1): 61–76 . doi : 10.1007/PL00009187 . ISSN 0178-4617 . S2CID 5409198 .  
  9. ↑ ليفي، برونو؛ موهايائي، رويا؛ فون هاوسغر، سيباستيان (13 يوليو 2021). "خوارزمية نقل مثالية شبه منفصلة سريعة لإعادة بناء فريدة للكون المبكر" . الإشعارات الشهرية للجمعية الفلكية الملكية . 506 (1): 1165-1185 . arXiv : 2012.09074 . doi : 10.1093/mnras/stab1676 . ISSN 0035-8711 . 
  10. ↑ ليفي، برونو (فبراير 2022). "النقل الأمثل الجزئي لشبكة لاغرانجية ذات حجم ثابت وحدود حرة" . مجلة الفيزياء الحاسوبية . 451 110838. arXiv : 2106.03936 . Bibcode : 2022JCoPh.45110838L . doi : 10.1016/j.jcp.2021.110838 . S2CID 235406800 . 
  11. ^ Fejes Tóth، L. (1977)، “إضاءة الأقراص المحدبة”، Acta Mathematica Academiae Scientiarum Hungaricae ، 29 ( 3– 4): 355–360 ، دوى : 10.1007 / BF01895856 ، السيد 0464065 ، S2CID 122510545  .
  12. ↑ أورينهامر، ف.؛ إيماي، هـ. (1988)، "العلاقات الهندسية بين مخططات فورونوي"، Geometriae Dedicata ، 27 (1): 65-75 ، doi : 10.1007/BF00181613 ، MR 0950323 .