نظام التحكم عن بعد

في الهندسة الحسابية ، نظام CC أو نظام عكس عقارب الساعة هو علاقة ثلاثية pqr قدمها دونالد كنوث لنمذجة الترتيب في اتجاه عقارب الساعة لثلاثيات من النقاط في وضع عام في المستوى الإقليدي . ^{[ 1 ]}

يُشترط أن يفي نظام CC بالبديهيات التالية، لجميع النقاط المتميزة p و q و r و s و t : ^{[ 2 ]}

1. التناظر الدوري: إذا كان pqr فإن qrp .
2. التناظر العكسي: إذا كان pqr فإن prq ليس .
3. عدم الانحلال: إما pqr أو prq .
4. الداخلية: إذا كان tqr و ptr و pqt ، فإن pqr .
5. خاصية التعدي: إذا كان tsp و tsq و tsr و tpq و tqr ، فإن tpr .

لا تُعتبر ثلاثيات النقاط غير المتميزة جزءًا من العلاقة.

يمكن تعريف نظام إحداثيات CC من أي مجموعة نقاط في المستوى الإقليدي ، بحيث لا تقع أي ثلاث نقاط منها على استقامة واحدة، وذلك بإضافة ثلاثية pqr من نقاط مختلفة إلى العلاقة، كلما رتبت هذه الثلاثية هذه النقاط الثلاث عكس اتجاه عقارب الساعة حول المثلث الذي تشكله. وباستخدام الإحداثيات الديكارتية للنقاط، تُضاف الثلاثية pqr إلى العلاقة تحديدًا عندما ^{[ 3 ]}

${\displaystyle \det \left({\begin{array}{ccc}x_{p}&y_{p}&1\\x_{q}&y_{q}&1\\x_{r}&y_{r}&1\end{array}}\right)>0.}$

إن الشرط الذي ينص على أن النقاط في وضع عام يعادل الشرط الذي ينص على أن محدد المصفوفة هذا لا يساوي الصفر أبدًا بالنسبة للنقاط المتميزة p و q و r .

ومع ذلك، لا ينشأ كل نظام CC من مجموعة نقاط إقليدية بهذه الطريقة. ^{[ 4 ]}

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

توجد علاقة تناظر ثنائية بين أنظمة CC والمصفوفات الموجهة غير الدورية المنتظمة من الرتبة 3. ^{[ 7 ]} وهذه المصفوفات بدورها لها علاقة تناظر أحادية مع فئات التكافؤ الطوبولوجي لترتيبات الخطوط الزائفة ذات الخلية المميزة الواحدة. ^{[ 6 ]}

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

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

عدد أنظمة CC غير المتماثلة على n نقطة هو ^{[ 6 ] [ 11 ]}

1، 1، 1، 2، 3، 20، 242، 6405، 316835، 28627261 ... (التسلسل A006246 في OEIS )

تنمو هذه الأرقام بشكل أسي في ^{n²؛ [12} ] في ^{المقابل ، ينمو} عدد أنظمة CC القابلة للتحقيق بشكل أسي فقط في Θ( n log n ). ^{[ 7 ]}  

وبشكل أدق، فإن عدد أنظمة CC غير المتماثلة C _n على n نقطة هو على الأكثر ^{[ 13 ].}

${\displaystyle 3^{\binom {n}{2}}.}$

يُرجّح كنوت بقوة أكبر أن هذه الأرقام تخضع للمتباينة التكرارية

${\displaystyle C_{n}\leq n2^{n-2}C_{n-1}.}$

• أيتشولزر، أوزوين؛ ميلتزو، تيلمان؛ بيلز، ألكسندر (2013)، "البحث عن النقاط القصوى وحواف التنصيف في أنواع الترتيب المجردة"، الهندسة الحسابية ، 46 (8): 970-978 ، doi : 10.1016/j.comgeo.2013.05.001 ، MR 3061458 ، PMC 3688538 ، PMID 24092953   .
• بيجيلزيمر، ألينا؛ رادزيسوفسكي، ستانيسواف (2002)، "حول تقسيم ترتيبات الخطوط إلى النصف"، الرياضيات المتقطعة ، 257 ( 2-3 ): 267-283 ، doi : 10.1016/S0012-365X(02)00430-2 ، MR 1935728 .
• كنوت، دونالد إي. (1992)، البديهيات والأغلفة ، سلسلة محاضرات في علوم الحاسوب، المجلد  606، هايدلبرغ: سبرينغر-فيرلاغ، الصفحات  9+109، doi : 10.1007/3-540-55611-7 ، ISBN 3-540-55611-7، MR 1226891 ، S2CID 5452191 ، مؤرشف من الأصل في 20 يونيو 2017 ، تم استرجاعه في 5 مايو 2011  .