نظرية رادون

في الهندسة ، تنص نظرية رادون حول المجموعات المحدبة ، التي نشرها يوهان رادون عام 1921، على ما يلي:

يمكن تقسيم أي مجموعة من d  +  2 نقطة في R ^d إلى مجموعتين تتقاطع أغلفةهما المحدبة .

تُسمى النقطة الواقعة في تقاطع هذه الأغلفة المحدبة بنقطة رادون للمجموعة.

على سبيل المثال، في حالة d  =  2، يمكن تقسيم أي مجموعة من أربع نقاط في المستوى الإقليدي بإحدى طريقتين. قد تشكل ثلاثية ومجموعة مفردة، حيث يحتوي الغلاف المحدب للثلاثية (مثلث) على المجموعة المفردة؛ أو قد تشكل زوجين من النقاط التي تشكل نهايتي قطعتين مستقيمتين متقاطعتين .

لنفترض أي مجموعة${\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}$لدينا d  +  2 نقطة في فضاء ذي d بُعد. عندئذٍ _، توجد مجموعة من المُضاعِفات a1 ، ...، ad _{+ 2} ، ليس جميعها أصفارًا، تُحَلُّ نظام المعادلات الخطية _.    

${\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}$

لأن هناك d  +  2 مجهولًا (المُضاعِفات)، ولكن d  +  1 معادلة فقط يجب أن تُحققها هذه المُضاعِفات (معادلة لكل إحداثية من إحداثيات النقاط، بالإضافة إلى معادلة نهائية تتطلب أن يكون مجموع المُضاعِفات صفرًا). لنُثبِّت حلًا غير صفري مُحددًا a ₁ ،  ...، a _{d + 2} .   ${\displaystyle I\subseteq X}$لتكن مجموعة النقاط ذات المعاملات الموجبة، ولتكن${\displaystyle J=X\setminus I}$لتكن مجموعة النقاط ذات المعاملات السالبة أو الصفرية.${\displaystyle I}$و${\displaystyle J}$قم بتشكيل التقسيم المطلوب للنقاط إلى مجموعتين فرعيتين مع أغلفة محدبة متقاطعة.

الأغلفة المحدبة لـ${\displaystyle I}$و${\displaystyle J}$يجب أن يتقاطعا، لأنهما يحتويان على النقطة

${\displaystyle p=\sum _{x_{i}\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{x_{j}\in J}{\frac {-a_{j}}{A}}x_{j},}$

أين

${\displaystyle A=\sum _{x_{i}\in I}a_{i}=-\sum _{x_{j}\in J}a_{j}.}$

الجانب الأيسر من الصيغة لـ${\displaystyle p}$يعبّر عن هذه النقطة كمجموعة محدبة من النقاط في${\displaystyle I}$ويعبّر الجانب الأيمن عن ذلك كتركيبة محدبة للنقاط في${\displaystyle J}$. لذلك،${\displaystyle p}$ينتمي إلى كلا الغلافين المحدبين، مما يكمل البرهان.

تتيح طريقة البرهان هذه إنشاء نقطة رادون بكفاءة، في وقت متعدد الحدود بالنسبة للبعد، باستخدام طريقة الحذف الغاوسي أو خوارزميات فعالة أخرى لحل نظام المعادلات للمضاعفات. ^{[ 1 ]}

الصيغة المكافئة لنظرية رادون هي:

إذا كانت ƒ أي دالة خطية من مجسم بسيط ذي ( d  +  1) أبعاد Δ ^d+1 إلى R ^d ، فإن هناك وجهين منفصلين لـ Δ ^d+1 تتقاطع صورهما تحت ƒ.

هما متكافئان لأن أي دالة تآلفية على مُجَسَّم بسيط تُحدَّد بشكل فريد بواسطة صور رؤوسه. رسميًا، لنفترض أن ƒ دالة تآلفية من Δ ^d+1 إلى R ^d .${\displaystyle v_{1},v_{2},\dots ,v_{d+2}}$لتكن رؤوس المثلث Δ ^d+1 ، ولتكن${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$تكون صورهم تحت ƒ . وفقًا للصياغة الأصلية، فإن${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$يمكن تقسيم المجموعة إلى مجموعتين فرعيتين منفصلتين، مثل ( xᵢ ₎ ᵢ _{في المجموعة I} و ( xⱼ _{) ⱼ في المجموعة J،} مع غلاف محدب متداخل. ولأن f دالة خطية، فإن الغلاف المحدب للمجموعة ( xᵢ ₎ ᵢ _{في المجموعة I} هو صورة الوجه الممتد من الرؤوس ( vᵢ ₎ ᵢ _{في المجموعة I ،} وبالمثل فإن الغلاف المحدب للمجموعة ( xⱼ ₎ ⱼ _{في المجموعة J} هو صورة الوجه الممتد من الرؤوس ( vⱼ )ⱼ _{في المجموعة j} . هذان الوجهان منفصلان، وتتقاطع صورهما تحت تأثير f - كما تنص عليه الصيغة الجديدة. تعمم نظرية رادون الطوبولوجية هذه الصيغة، إذ تسمح بأن تكون f أي دالة متصلة - ليس بالضرورة خطية: ^{[ 2 ]}

إذا كانت ƒ أي دالة متصلة من مجسم بسيط ذي ( d  +  1) أبعاد Δ ^d+1 إلى R ^d ، فإن هناك وجهين منفصلين لـ Δ ^d+1 تتقاطع صورهما تحت ƒ.

بشكلٍ أعم، إذا كانت K أي مجموعة محدبة مضغوطة ذات بُعد ( d  +  1)، وكانت ƒ أي دالة متصلة من K إلى فضاء ذي بُعد d ، فإنه توجد دالة خطية g بحيث تُسقط الدالة ƒ نقطةً عندها تحقق g قيمتها القصوى ونقطةً أخرى عندها تحقق g قيمتها الدنيا على نفس النقطة. في حالة كون K مُجَسَّمًا بسيطًا، فإن وجهي المُجَسَّم البسيط المُشكَّلين من نقطتي g القصوى والدنيا يجب أن يكونا وجهين منفصلين، وصورتيهما تتقاطعان تقاطعًا غير فارغ. هذه العبارة العامة نفسها، عند تطبيقها على كرة فائقة بدلًا من مُجَسَّم بسيط، تُعطي نظرية بورزوك-أولام ، التي تنص على أن ƒ يجب أن تُسقط نقطتين متقابلتين على الكرة على نفس النقطة. ^{[ 2 ]}

نقطة رادون لأي أربع نقاط في المستوى هي الوسيط الهندسي لها ، أي النقطة التي تقلل مجموع المسافات إلى النقاط الأخرى. ^{[ 5 ] [ 6 ]}

Radon's theorem forms a key step of a standard proof of Helly's theorem on intersections of convex sets;^[7] this proof was the motivation for Radon's original discovery of Radon's theorem.

Radon's theorem can also be used to calculate the VC dimension of d-dimensional points with respect to linear separations. There exist sets of d + 1 points (for instance, the points of a regular simplex) such that every two nonempty subsets can be separated from each other by a hyperplane. However, no matter which set of d + 2 points is given, the two subsets of a Radon partition cannot be linearly separated. Therefore, the VC dimension of this system is exactly d + 1.^[8]

A randomized algorithm that repeatedly replaces sets of d + 2 points by their Radon point can be used to compute an approximation to a centerpoint of any point set, in an amount of time that is polynomial in both the number of points and the dimension.^[1]

Geometric median. The Radon point of three points in a one-dimensional space is just their median. The geometric median of a set of points is the point minimizing the sum of distances to the points in the set; it generalizes the one-dimensional median and has been studied both from the point of view of facility location and robust statistics. For sets of four points in the plane, the geometric median coincides with the Radon point.

Tverberg's theorem. A generalization for partition into r sets was given by HelgeTverberg (1966) and is now known as Tverberg's theorem. It states that for any set of ${\displaystyle (d+1)(r-1)+1\ }$points in Euclidean d-space, there is a partition into r subsets whose convex hulls intersect in at least one common point.

Carathéodory's theorem states that any point in the convex hull of some set of points is also within the convex hull of a subset of at most d + 1 of the points; that is, that the given point is part of a Radon partition in which it is a singleton. One proof of Carathéodory's theorem uses a technique of examining solutions to systems of linear equations, similar to the proof of Radon's theorem, to eliminate one point at a time until at most d + 1 remain.

الهندسات المحدبة . تمّ أيضًا دراسة المفاهيم المتعلقة بنظرية رادون فيما يخصّ الهندسات المحدبة ، وهي عائلات من المجموعات المنتهية التي تتميّز بأنّ تقاطع أيّ مجموعتين في العائلة يبقى ضمنها، وأنّ المجموعة الفارغة واتحاد جميع المجموعات ينتميان إلى العائلة. في هذا السياق الأعمّ، يُعرَّف الغلاف المحدب لمجموعة S بأنه تقاطع عناصر العائلة التي تحتوي على S ، ويُعرَّف عدد رادون لفضاء ما بأنه أصغر قيمة لـ r بحيث يكون لأيّ r نقطة مجموعتان جزئيتان يتقاطع غلافهما المحدب. وبالمثل، يمكن تعريف عدد هيلي h وعدد كاراثيودوري c قياسًا على تعريفاتهما للمجموعات المحدبة في الفضاءات الإقليدية، ويمكن إثبات أنّ هذين العددين يحققان المتباينتين h  < r ≤ ch + 1. ^{[ 9 ]}     

نظرية رادون للرسوم البيانية . في أي رسم بياني غير موجه ، يمكن تعريف المجموعة المحدبة بأنها مجموعة من الرؤوس تشمل كل مسار مُستحث يربط بين أي زوج من الرؤوس في المجموعة. وفقًا لهذا التعريف، يمكن تقسيم أي مجموعة من ω + 1 رأسًا في الرسم البياني إلى مجموعتين فرعيتين تتقاطع أغلفةهما المحدبة، وω + 1 هو الحد الأدنى الذي يسمح بذلك، حيث ω هو عدد الزمر في الرسم البياني المُعطى. ^{[ 10 ]} للاطلاع على نتائج ذات صلة تتضمن أقصر المسارات بدلًا من المسارات المُستحثة، انظر تشيبوي (1986) وباندلت وبيش (1989) .    

• باجموتشي، على سبيل المثال؛ باراني، آي. (1979)، “تعميم مشترك لنظرية بورسوك ورادون”، Acta Mathematica Hungarica ، 34 ( 3– 4): 347– 350، دوى : 10.1007 / BF01896131 ، S2CID 12971298 .
• باندلت، H.-J.؛ Pesch، E. (1989)، “نظرية الرادون للرسوم البيانية هيلي”، Archiv der Mathematik ، 52 (1): 95–98 ، doi : 10.1007/BF01197978 ، S2CID 120983560 .
• تشيبوي، ف.د. (1986)، "بعض خصائص التحدب من الدرجة د في الرسوم البيانية المثلثية"، مات . إيسليد. (باللغة الروسية)، 87 : 164-177. كما ذكر باندلت وبيش (1989) .
• كلاركسون، كينيث ل .؛ إبستين، ديفيد ؛ ميلر، غاري ل .؛ ستورتيفانت، كارل؛ تينغ، شانغ هوا (1996)، "تقريب النقاط المركزية باستخدام نقاط رادون المتكررة" ، المجلة الدولية للهندسة الحسابية والتطبيقات ، 6 (3): 357-377 ، doi : 10.1142/s021819599600023x ، MR 1409651 .
• دانزر، ل.؛ غرونباوم، ب .؛ كلي، ف. ( 1963)، "نظرية هيلي وما يتصل بها"، التحدب ، وقائع ندوة الرياضيات البحتة، المجلد  7، الجمعية الرياضية الأمريكية ، الصفحات 101-179 .
• دوشيه، بيير (1987)، "المجموعات المحدبة في الرسوم البيانية. الجزء الثاني: التحدب الأدنى للمسار"، مجلة نظرية التوافيق، السلسلة أ ، 44 (3): 307-316 ، doi : 10.1016/0095-8956(88)90039-1. كما ذكر باندلت وبيش (1989) .
• إيكهوف، ج. ( 1993)، "نظريات من نوع هيلي، رادون، وكاراثيودوري"، كتيب الهندسة المحدبة ، المجلد  أ، ب، أمستردام: نورث هولاند، ص 389-448 .
• كاي، ديفيد سي؛ وومبل، يوجين دبليو (1971)، "نظرية التحدب البديهية والعلاقات بين أعداد كاراثيودوري وهيلي ورادون" ، مجلة المحيط الهادئ للرياضيات ، 38 (2): 471-485 ، doi : 10.2140/pjm.1971.38.471 ، MR 0310766 .
• ماتوشيك، ج. (2002)، "1.3 ليمّة رادون ونظرية هيلي"، محاضرات في الهندسة المتقطعة ، نصوص الدراسات العليا في الرياضيات ، المجلد  212، سبرينغر-فيرلاغ، الصفحات 9-12 ، ISBN  978-0-387-95373-1.
• ماتوشيك، ج. (2003)، "5.1 نظريات عدم التضمين: مقدمة"، استخدام نظرية بورزوك-أولام: محاضرات حول الطرق الطوبولوجية في التوافقية والهندسة ، سبرينغر-فيرلاغ، ص 88-92 .
• Radon، J. (1921)، “Mengen konvexer Körper، die einen Gemeinsamen Punkt enthalten”، Mathematische Annalen ، 83 ( 1– 2): 113– 115، دوى : 10.1007 / BF01464231 ، S2CID 121627696 .
• تفيربيرغ، هـ. (1966)، "تعميم لنظرية رادون"، مجلة جمعية لندن الرياضية ، 41 : 123-128 ، doi : 10.1112/jlms/s1-41.1.123.