ترتيب الخطوط

في الهندسة، يُعرَّف ترتيب الخطوط بأنه تقسيم المستوى الإقليدي بواسطة مجموعة منتهية من الخطوط. يتكون الترتيب من مضلعات محدبة محدودة وغير محدودة ، وهي خلايا الترتيب، وقطع مستقيمة وأشعة ، وهي حواف الترتيب ، ونقاط تقاطع خطين أو أكثر، وهي رؤوس الترتيب. عند النظر إلى الترتيب في المستوى الإسقاطي بدلاً من المستوى الإقليدي، يتقاطع كل خطين، ويكون الترتيب هو الثنائي الإسقاطي لمجموعة منتهية من النقاط. كما دُرست ترتيبات الخطوط في المستوى الزائدي ، وعُمِّمت لتشمل الخطوط الزائفة ، وهي منحنيات لها خصائص طوبولوجية مشابهة للخطوط. يُنسب الفضل في الدراسة الأولية للترتيبات إلى ورقة بحثية نشرها جاكوب شتاينر عام 1826 .

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

تُعدّ الأعداد القصوى للخلايا والحواف والرؤوس، في الترتيبات التي تتضمن عددًا معينًا من الخطوط، دوالًا تربيعية لعدد الخطوط. وتُحقق هذه القيم القصوى من خلال الترتيبات البسيطة. وقد دُرست تعقيدات خصائص أخرى للترتيبات في الهندسة المتقطعة ؛ وتشمل هذه الخصائص المناطق (الخلايا المتلامسة مع خط واحد)، والمستويات (السلاسل المضلعة التي يمر أسفلها عدد معين من الخطوط). وتتعلق نظرية روبرتس للمثلث ومسألة كوبون للمثلث بالحد الأدنى والحد الأقصى لعدد الخلايا المثلثية في الترتيب الإقليدي، على التوالي.

تُعرف الخوارزميات في الهندسة الحسابية بقدرتها على بناء خصائص الترتيب في وقت يتناسب مع عدد الخصائص، وفي مساحة تتناسب خطيًا مع عدد الخطوط. كما درس الباحثون خوارزميات فعّالة لبناء أجزاء أصغر من الترتيب، ولحلّ مسائل مثل مسألة أقصر مسار على رؤوس وحواف الترتيب.

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

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

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

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

من السهل حساب الحد الأقصى لعدد الرؤوس والحواف والخلايا في الترتيب، وكلها تتناسب طرديًا مع مربع عدد الخطوط:

• اتفاق مع${\displaystyle n}$الخطوط تحتوي على الأكثر${\displaystyle n(n-1)/2}$عدد الرؤوس ( عدد مثلثي )، رأس واحد لكل زوج من الخطوط المتقاطعة. يتحقق هذا الحد الأقصى في الترتيبات البسيطة ، أي تلك التي يتقاطع فيها كل خطين عند رأس منفصل عن جميع الخطوط الأخرى. يقل عدد الرؤوس عندما تكون بعض الخطوط متوازية، أو عندما يتقاطع بعض الرؤوس مع أكثر من خطين. ^{[ 4 ]}
• يمكن تدوير الترتيب، إذا لزم الأمر، لتجنب الخطوط المتوازية مع المحاور. بعد هذه الخطوة، يمتد كل شعاع يشكل حافة الترتيب إما لأعلى أو لأسفل من نقطة نهايته؛ ولا يمكن أن يكون أفقيًا.${\displaystyle n}$أشعة متجهة للأسفل، شعاع واحد لكل سطر، وهذه الأشعة تفصل${\displaystyle n+1}$الخلايا في هذا الترتيب غير محدودة في الاتجاه السفلي. أما الخلايا المتبقية فلها رأس سفلي فريد (وذلك لعدم وجود خطوط موازية للمحور). لكل زوج من الخطوط، لا يمكن أن توجد إلا خلية واحدة حيث يلتقي الخطان عند الرأس السفلي، لذا فإن عدد الخلايا المحدودة في الاتجاه السفلي لا يتجاوز عدد أزواج الخطوط .${\displaystyle n(n-1)/2}$بإضافة الخلايا غير المحدودة والمحدودة، يمكن أن يكون العدد الإجمالي للخلايا في الترتيب على الأكثر${\displaystyle n(n+1)/2+1}$[ ^{5 ]} هذه هي أرقام ^تسلسل متعهد الطعام الكسول . ^{[ 6 ]}
• عدد حواف الترتيب هو على الأكثر${\displaystyle n^{2}}$، كما يمكن ملاحظته إما باستخدام خاصية أويلر لحسابها من عدد الرؤوس والخلايا، أو بملاحظة أن كل خط مقسم إلى أكثر من${\displaystyle n}$حواف من جانب الآخر${\displaystyle n-1}$ lines. Simple arrangements have exactly ${\displaystyle n^{2}}$ edges.^[5]

More complex features go by the names of "zones", "levels", and "many faces":

• The zone of a line ${\displaystyle \ell }$ in a line arrangement is the collection of cells having edges belonging to ${\displaystyle \ell }$. The zone theorem states that the total number of edges in the cells of a single zone is linear. More precisely, the total number of edges of the cells belonging to a single side of line ${\displaystyle \ell }$ is at most ${\displaystyle 5n-1}$,^[7] and the total number of edges of the cells belonging to both sides of ${\displaystyle \ell }$ is at most ${\displaystyle \lfloor 9.5n\rfloor -1}$.^[8] More generally, the total complexity of the cells of a line arrangement that are intersected by any convex curveis ${\displaystyle O(n\alpha (n))}$, where ${\displaystyle \alpha }$ denotes the inverse Ackermann function, as may be shown using Davenport–Schinzel sequences.^[9] The sum of squares of cell complexities in an arrangement is ${\displaystyle O(n^{2})}$, as can be shown by summing the zones of all lines.^[10]
• The ${\displaystyle k}$-level of an arrangement is the polygonal chain formed by the edges that have exactly ${\displaystyle k}$ other lines directly below them. The ${\displaystyle \leq k}$-level is the portion of the arrangement below the ${\displaystyle k}$-level. Finding matching upper and lower bounds for the complexity of a ${\displaystyle k}$-level remains a major open problem in discrete geometry. The best upper bound known is ${\displaystyle O(nk^{1/3})}$, while the best lower bound known is ${\displaystyle n2^{\Omega ({\sqrt {\log k}})}}$.^[11] In contrast, the maximum complexity of the ${\displaystyle \leq k}$-level is known to be ${\displaystyle \Theta (nk)}$.^[12] A ${\displaystyle k}$-level is a special case of a monotone path in an arrangement; that is, a sequence of edges that intersects any vertical line in a single point. However, monotone paths may be much more complicated than ${\displaystyle k}$-levels: there exist arrangements and monotone paths in these arrangements where the number of points at which the path changes direction is ${\displaystyle n^{2-o(1)}}$.^[13]
• Although a single cell in an arrangement may be bounded by all ${\displaystyle n}$ lines, it is not possible in general for ${\displaystyle m}$ different cells to all be bounded by ${\displaystyle n}$ lines. Rather, the total complexity of ${\displaystyle m}$ cells is at most ${\displaystyle \Theta (m^{2/3}n^{2/3}+n)}$[ ^{14 ] وهو} حدٌّ يكاد يكون مماثلاً للحدّ الوارد في نظرية سزيميريدي-تروتر بشأن تقاطعات النقاط مع الخطوط في المستوى. ويتبع برهانٌ بسيطٌ على ذلك من متباينة عدد التقاطعات : ^{[ 15 ]} إذا${\displaystyle m}$تحتوي الخلايا على ما مجموعه${\displaystyle x+n}$يمكن تشكيل رسم بياني باستخدام الحواف${\displaystyle m}$العقد (عقدة واحدة لكل خلية) و${\displaystyle x}$الحواف (حافة واحدة لكل زوج من الخلايا المتتالية على نفس الخط). يمكن رسم حواف هذا الرسم البياني كمنحنيات لا تتقاطع داخل الخلايا المقابلة لنهاياتها، ثم تتبع خطوط الترتيب. لذلك، يوجد${\displaystyle O(n^{2})}$توجد تقاطعات في هذا الرسم. ومع ذلك، وفقًا لمتباينة عدد التقاطعات، هناك${\displaystyle \Omega (x^{3}/m^{2})}$التقاطعات. من أجل تلبية كلا الحدين،${\displaystyle x}$يجب أن يكون${\displaystyle O(m^{2/3}n^{2/3})}$[ ^{16 ]​}

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

يمكن تفسير ترتيب الخطوط في المستوى الإقليدي بشكل طبيعي على أنه ترتيب للدوائر العظمى على الكرة ثنائية الأبعاد.${\displaystyle S^{2}}$لرؤية ذلك، قم بتضمين المستوى الإقليدي${\displaystyle \mathbb {R} ^{2}}$كمستوى أفيني${\displaystyle A\subset \mathbb {R} ^{3}}$لا تمر عبر نقطة الأصل. كل نقطة من${\displaystyle A}$يحدد خطًا يمر بنقطة الأصل، ويتقاطع معها${\displaystyle S^{2}}$في زوج من النقاط المتقابلة؛ وبالمثل، كل خط في${\displaystyle A}$تُشير الخرائط إلى دائرة عظمى على الكرة الأرضية. خط الاستواء المرتبط بـ${\displaystyle A}$يفصل بين نصفي الكرة الأرضية ويلعب دور الخط عند اللانهاية. تحديد النقاط المتقابلة على${\displaystyle S^{2}}$ينتج المستوى الإسقاطي، حيث الخطوط في${\displaystyle \mathbb {R} ^{2}}$تمتد بشكل طبيعي إلى دوائر عظمى، وتلتقي الخطوط المتوازية عند اللانهاية. وبهذه الطريقة، يتم الحفاظ على البنية التوافقية لترتيبات الخطوط، بما في ذلك نقاط التقاطع والمناطق والتقاطعات، عند نقلها إلى ترتيبات الدوائر العظمى على الكرة. ^{[ 20 ]}

بفضل الازدواجية الإسقاطية ، يُمكن فهم العديد من العبارات المتعلقة بالخصائص التوافقية للنقاط في المستوى بسهولة أكبر في صيغة ثنائية مكافئة تتعلق بترتيبات الخطوط. على سبيل المثال، تتحول نظرية سيلفستر-غالاي ، التي تنص على أن أي مجموعة نقاط غير متوازية في المستوى تحتوي على خط عادي يضم نقطتين فقط، تحت تأثير الازدواجية الإسقاطية إلى عبارة مفادها أن أي ترتيب إسقاطي لعدد محدود من الخطوط بأكثر من رأس واحد يحتوي على نقطة عادية ، وهي رأس يتقاطع عنده خطان فقط. وقد استخدم إيبرهارد ميلخيور ، في أقدم برهان معروف لنظرية سيلفستر-غالاي عام 1940 ، خاصية أويلر لإثبات أن مثل هذا الرأس يجب أن يكون موجودًا دائمًا. ^{[ 21 ]}

يُقال إن ترتيب الخطوط في المستوى الإسقاطي بسيط إذا كانت كل خلية من خلايا هذا الترتيب محاطة بثلاثة أضلاع فقط. وقد درس ميلخيور الترتيبات البسيطة لأول مرة. ^{[ 22 ]} وتُعرف ثلاث عائلات لانهائية من ترتيبات الخطوط البسيطة:

1. قلم رصاص شبه كامل يتكون من${\displaystyle n-1}$خطوط تمر بنقطة واحدة، بالإضافة إلى خط إضافي لا يمر بنفس النقطة،
2. عائلة الخطوط التي تشكلها أضلاع المضلع المنتظم مع محاور تناظره ، و
3. أضلاع ومحاور التناظر لمضلع منتظم زوجي، بالإضافة إلى الخط عند اللانهاية.

بالإضافة إلى ذلك، توجد أمثلة أخرى كثيرة لترتيبات تبسيطية متفرقة لا تنتمي إلى أي عائلة لانهائية معروفة. ^{[ 23 ]} يُفترض أن عددها محدود. ومن المعروف أن هذا صحيح في ظل حد خطي لعدد النقاط المزدوجة. ^{[ 24 ]} وكما كتب برانكو غرونباوم ، فإن الترتيبات التبسيطية "تظهر كأمثلة أو أمثلة مضادة في العديد من سياقات الهندسة التوافقية وتطبيقاتها". ^{[ 25 ]} على سبيل المثال، تُشكل الترتيبات التبسيطية أمثلة مضادة لتخمين حول العلاقة بين درجة مجموعة من المعادلات التفاضلية وعدد الخطوط الثابتة التي قد تحتويها هذه المعادلات. ^{[ 26 ]} المثالان المضادان المعروفان لتخمين ديراك-موتزكين (الذي ينص على أن أي${\displaystyle n}$يحتوي ترتيب السطر على الأقل${\displaystyle n/2}$النقاط العادية) كلاهما تبسيطي. ^{[ 27 ]}

يحتوي الرسم البياني الثنائي لترتيب خطي على عقدة واحدة لكل خلية وحافة واحدة تربط أي زوج من الخلايا التي تشترك في حافة من الترتيب. هذه الرسوم البيانية هي مكعبات جزئية ، وهي رسوم بيانية يمكن فيها تسمية العقد بواسطة متجهات ثنائية بحيث تكون مسافة الرسم البياني مساوية لمسافة هامينغ بين التسميات. في حالة الترتيب الخطي، تُعيّن كل إحداثية من إحداثيات التسمية القيمة 0 للعقد على أحد جانبي أحد الخطوط والقيمة 1 للعقد على الجانب الآخر. ^{[ 28 ]} استُخدمت الرسوم البيانية الثنائية للترتيبات التبسيطية لإنشاء عائلات لانهائية من المكعبات الجزئية المنتظمة من الدرجة 3 ، المتماثلة مع رسوم بيانية للمجسمات الزونوهيدرية البسيطة . ^{[ 29 ]}

ترتيب بأقل عدد من المثلثات وفقًا لنظرية روبرتس للمثلث

مثلثات كوبون مرتبة في 17 صفًا

من المهم أيضًا دراسة الأعداد القصوى للخلايا المثلثية في ترتيبات قد لا تكون بالضرورة تبسيطية. يجب أن يحتوي أي ترتيب في المستوى الإسقاطي على الأقل على${\displaystyle n}$المثلثات. كل ترتيب يحتوي فقط على${\displaystyle n}$يجب أن تكون المثلثات بسيطة. ^{[ 30 ]} بالنسبة للترتيبات الإقليدية بدلاً من الإسقاطية، يكون الحد الأدنى لعدد المثلثات هو${\displaystyle n-2}$، وفقًا لنظرية روبرتس للمثلث . ^{[ 31 ]} من المعروف أن الحد الأقصى لعدد الأوجه المثلثية الممكنة في ترتيب بسيط محدود من الأعلى بـ${\displaystyle n(n-1)/3}$والحد الأدنى هو${\displaystyle n(n-3)/3}$يتم تحقيق الحد الأدنى بواسطة مجموعات فرعية معينة من أقطار مصفوفة منتظمة${\displaystyle 2n}$-مضلع. ^{[ 32 ]} بالنسبة للترتيبات الإسقاطية التي لا يشترط أن تكون بسيطة، توجد ترتيبات ذات${\displaystyle n(n-1)/3+4}$مثلثات للجميع${\displaystyle n\geq 4}$وجميع الترتيبات مع${\displaystyle n\geq 6}$على الأكثر${\displaystyle 7n(n-1)/18+1/3}$المثلثات. ^{[ 33 ]} تسأل مسألة مثلث كوبون، ذات الصلة الوثيقة، عن أكبر عدد من المثلثات المحدودة غير المتداخلة في ترتيب على المستوى الإقليدي، دون احتساب الأوجه غير المحدودة التي قد تُشكّل مثلثات في المستوى الإسقاطي. ومرة ​​أخرى، لا يُشترط أن تكون الترتيبات بسيطة. بالنسبة لبعض قيم، وليس كل قيم ،${\displaystyle n}$توجد ترتيبات مع${\displaystyle n(n-2)/3}$المثلثات. ^{[ 34 ]}

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

في ورقة بحثية نُشرت عام 1981 ، قام إن جي دي بروين بدراسة حالات خاصة من هذا التصميم حيث يتكون ترتيب الخطوط من${\displaystyle k}$مجموعات من الخطوط المتوازية متساوية التباعد. بالنسبة لمجموعتين متعامدتين من الخطوط المتوازية، يُنتج هذا البناء تبليطًا مربعًا للمستوى، وبالنسبة لثلاث مجموعات من الخطوط بزوايا 120 درجة عن بعضها البعض (والتي تُشكل بدورها تبليطًا ثلاثيًا سداسيًا )، يُنتج هذا البناء تبليطًا معينيًا . ومع ذلك، بالنسبة لمزيد من مجموعات الخطوط، يُنتج هذا البناء تبليطات غير دورية . على وجه الخصوص، بالنسبة لخمس مجموعات من الخطوط بزوايا متساوية عن بعضها البعض (أو ما يُسميه دي بروين " شبكة خماسية" )، يُنتج هذا البناء مجموعة من التبليطات التي تتضمن النسخة المعينية من تبليطات بنروز . ^{[ 36 ]}

بلاط مربع رباعي الطبقات

تبليط مثلثي

تبليط سداسي مقسم إلى نصفين

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

يعني بناء ترتيب ما، عند إدخال قائمة بالخطوط في الترتيب، حساب تمثيل للرؤوس والحواف والخلايا الخاصة بالترتيب، بالإضافة إلى العلاقات المجاورة بين هذه العناصر. على سبيل المثال، يمكن تمثيل هذه الميزات كقائمة حواف متصلة ثنائياً . يمكن بناء الترتيبات بكفاءة باستخدام خوارزمية تزايدية تضيف خطًا واحدًا في كل مرة إلى ترتيب الخطوط المضافة سابقًا. يمكن إضافة كل خط جديد في وقت يتناسب مع حجم منطقته، وهو خطي وفقًا لنظرية المنطقة. ينتج عن ذلك وقت بناء إجمالي قدره${\displaystyle O(n^{2})}$[ ^{7 ]} متطلبات الذاكرة لهذه الخوارزمية هي ^أيضًا${\displaystyle O(n^{2})}$بدلاً من ذلك، من الممكن الإبلاغ عن خصائص الترتيب دون تخزينها كلها دفعة واحدة، في الوقت المناسب .${\displaystyle O(n^{2})}$والمساحة​${\displaystyle O(n)}$باستخدام تقنية حسابية تُعرف بالمسح الطوبولوجي. ^{[ 38 ]} يتطلب حساب ترتيب الخطوط بدقة دقة عددية تفوق دقة إحداثيات الإدخال بعدة مرات: فإذا تم تحديد خط بنقطتين عليه، فقد تحتاج إحداثيات رؤوس الترتيب إلى دقة تفوق دقة هاتين النقطتين بأربعة أضعاف. لذلك ، درس علماء الهندسة الحسابية أيضًا خوارزميات لإنشاء ترتيبات بدقة عددية محدودة. ^{[ 39 ]}

كما قام الباحثون بدراسة الخوارزميات الفعالة لإنشاء أجزاء أصغر من الترتيب، مثل المناطق، ^{[ 40 ]}${\displaystyle k}$المستويات، ^{[ 41 ]} أو مجموعة الخلايا التي تحتوي على مجموعة معينة من النقاط. ^{[ 42 ]} مشكلة إيجاد ترتيب الرؤوس مع الوسيط${\displaystyle x}$تظهر الإحداثيات (بصيغة ثنائية) في الإحصاءات القوية كمشكلة حساب مقدر ثيل-سين لمجموعة من النقاط. ^{[ 43 ]}

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

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

ترتيب خط زائد مكافئ توافقيًا لمخطط الوتر الذي استخدمه Ageev (1996) لإظهار أن الرسوم البيانية الدائرية الخالية من المثلثات قد تحتاج أحيانًا إلى 5 ألوان .

ترتيب الخطوط الزائفة هو مجموعة من المنحنيات التي تشترك في خصائص طوبولوجية مماثلة مع ترتيب الخطوط. ^{[ 48 ]} يمكن تعريف هذه المنحنيات في المستوى الإسقاطي على أنها منحنيات مغلقة بسيطة، يتقاطع أي منحنيين منها في نقطة واحدة. ^{[ 49 ]} يُقال إن ترتيب الخطوط الزائفة قابل للتمدد إذا كان مكافئًا توافقيًا لترتيب الخطوط. يُعد تحديد قابلية التمدد مهمة حسابية معقدة: إذ يتطلب الأمر من النظرية الوجودية للأعداد الحقيقية التمييز بين الترتيبات القابلة للتمدد وغير القابلة للتمدد. ^{[ 50 ]} يمكن تمديد أي ترتيب لعدد محدود من الخطوط الزائفة بحيث تصبح خطوطًا في "امتداد"، وهو نوع من هندسة التلاقي غير الإقليدية حيث يتم توصيل كل نقطتين في مستوى طوبولوجي بخط فريد (كما هو الحال في المستوى الإقليدي)، ولكن قد لا تنطبق عليه بديهيات أخرى من الهندسة الإقليدية. ^{[ 51 ]}

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

في دراسة استقصائية حول الترتيبات، نسب بانكاج أغاروال وميشا شارير دراسة الترتيبات إلى جاكوب شتاينر ، وكتبا أن "أول ورقة بحثية في هذا الموضوع ربما تكون" ورقة بحثية لشتاينر نُشرت عام 1826. ^{[ 56 ]} في هذه الورقة، أثبت شتاينر حدودًا لأقصى عدد من السمات من الأنواع المختلفة التي قد يمتلكها الترتيب. ^{[ 57 ]} بعد شتاينر، اتجهت دراسة الترتيبات نحو ترتيبات المستويات الفائقة ذات الأبعاد الأعلى ، مع التركيز على بنيتها العامة وعلى الخلايا المفردة في هذه الترتيبات. عادت دراسة ترتيبات الخطوط، والسمات الأكثر تعقيدًا مثل المناطق داخل هذه الترتيبات، إلى الاهتمام بدءًا من ثمانينيات القرن العشرين كجزء من أسس الهندسة الحاسوبية . ^{[ 56 ]}

• التكوين (في الهندسة) ، هو ترتيب للخطوط ومجموعة من النقاط بحيث تحتوي جميع الخطوط على نفس عدد النقاط، وتنتمي جميع النقاط إلى نفس عدد الخطوط.
• الترتيب (تقسيم الفضاء) ، هو تقسيم للمستوى بواسطة منحنيات متراكبة أو لفضاء ذي أبعاد أعلى بواسطة أسطح متراكبة، دون اشتراط أن تكون المنحنيات أو الأسطح مستوية.
• الجسر الرياضي ، وهو جسر في كامبريدج بإنجلترا، تشكل عوارضه ترتيبًا من الخطوط المماسية لقوسه.

• قاعدة بيانات لترتيبات الخطوط المختلفة توافقياً