التقسيم المتوافق لمضلع مستقيم من الرتبة n (قد يحتوي على ثقوب) هو تقسيم P إلى مستطيلات دون استخدام نقاط شتاينر (أي يجب أن تقع كل زوايا جميع المستطيلات على حدود P). عدد الطعن لهذا التقسيم هو العدد الأقصى للمستطيلات التي يتقاطع معها مقطع محوري مستوي داخل P. في هذه الورقة، نفحص مشكلة حساب التقسيمات المتوافقة ذات عدد الطعن المنخفض. نظهر أن حساب تقسيم متوافق بعدد طعن لا يتجاوز 4 هو مسألة NP-صعبة، مما يعزز نتيجة صعوبة معروفة سابقاً (Durocher & Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)) ويقضي على إمكانية وجود خوارزميات قابلة للمعالجة بمعاملات ثابتة معلمة بعدد الطعن ما لم يكن P = NP. بالمقابل، نقدم (1) خوارزمية زمنها O ( n log n ) لتقرير إمكانية وجود تقسيم متوافق بعدد طعن 2، (2) خوارزمية قابلة للمعالجة بمعاملات ثابتة معلمة بعدد الطعن وعرض الشجرة لرسم البكسل للمضلع، و (3) خوارزمية قابلة للمعالجة بمعاملات ثابتة معلمة بعدد الطعن للمضلعات بدون ثقوب في وضع عام.
درس Biedl وآخرون هذا السؤال.