इष्टतम नकारात्मक स्थान?

Question

बड़े आयताकार आर के अंदर आयताकार आर [] दिया गया है, क्या आर [] के बीच "negative space" भरने वाले आयतों की न्यूनतम संख्या निर्धारित करने के लिए एक इष्टतम तेज़ एल्गोरिदम है?

उदाहरण के लिए, बैंगनी आयत के अंदर इन तीन नीले आयत दिया:

कैसे मैं जल्दी से (नीचे हरे रंग में इस तरह की आयतों की एक सूची जो इष्टतम विन्यास नहीं हो सकता है यह समझ सकते हैं, इसलिए मेरी पोस्ट):

Answer 1

क्या oosterwal का वर्णन करता है समलम्बाकार अपघटन की एक विशेष मामला है, एक अच्छी तरह से समझ में आ computati में आदिम ऑनल ज्यामिति आमतौर पर एक प्लानर उपखंड में बिंदु स्थान के लिए उपयोग की जाती है। इसे उचित स्थिरता के साथ समय ओ (एन लॉग एन) में कार्यान्वित किया जा सकता है।

जब आयताकार सामान्य स्थिति में होते हैं, तो यह # हरे आयताकार = 3 * # नीले आयताकार + 1 के साथ "आयत" वापस कर देगा, और यह इष्टतम है। प्रत्येक नीले कोने के एल-आकार वाले पड़ोस को को एक दिशा में या दूसरे को एक हरे रंग के खंड में काट दिया जाना चाहिए (सामान्य स्थिति: हम दो नीले आयताकारों के लिए एक ही सेगमेंट का उपयोग नहीं कर सकते हैं), इसलिए प्रत्येक नीले आयताकार के लिए, हम जोड़ते हैं 4 हरे रंग के किनारों 8 हरे रंग के किनारों और 4 शिखर (4 नए किनारों के साथ 4 उप-विभाजित), प्रक्रिया में 1 से जुड़े घटकों की संख्या घटाना। पॉलीहेड्रल फॉर्मूला का परिणाम 3 और चेहरे (आयताकार) है:

वी - ई + एफ = 1 + # जुड़े घटक।

---

उदाहरण:

abc 
0+-----------+ 
1|   | 
2| +--+  | 
3| |R | +-+ | 
4| +--+ |S| | 
5|  | | | 
6| +--+ | | | 
7| |T | +-+ | 
8| +--+  | 
9+-----------+ 

हम ऊपर से नीचे तक एक झाडू लाइन चला रहे हैं। प्रतियोगिताएं हैं

# (y, whichside, xmin, xmax) 
(2, top, 3, 6) # R 
(3, top, 8, a) # S 
(4, bot, 3, 6) # R 
(6, top, 2, 5) # T 
(7, bot, 8, a) # S 
(8, bot, 2, 5) # T 

हम एक द्विआधारी खोज वृक्ष एक्स द्वारा आदेश दिया कि आंशिक रूप से निर्माण किया हरी आयतों रखती है की स्थापना की। मैं इसे एक सूची के रूप में लिखूंगा।

# (xmin, xmax, ymin) 
(0, c, 0) 

अब हम घटनाओं को संसाधित करना शुरू करते हैं। पहला है (2, शीर्ष, 3, 6)। हम पाते हैं कि यह अब तक केवल हरे आयत के अंदर घोंसला है, (xmin = 0, xmax = c, ymin = 0, ymax = 2)। (नीला अंतराल हमेशा जब तक नीले आयत एक दूसरे को काटना नहीं है के रूप में घोंसले।) हम दो नए हरी आयत, नीले आयत के प्रत्येक पक्ष पर एक प्रारंभ करें, और खोज पेड़ शामिल

(0, 3, 2) (6, c, 2) 

अब हम पर कार्रवाई (3, शीर्ष, 8, ए)। अंतराल (8, क) के अंदर घोंसले (6, ग), तो हम एक और आयत खत्म (xmin = 6, xmax = ग, ymin = 2, ymax = 3) और दो और शुरू:

(0, 3, 2) (6, 8, 3) (a, c, 3) 

अब हम प्रक्रिया (4, बॉट, 3, 6)। यह हरे आयतों को अपने बाएं और दाएं, (xmin = 0, xmax = 3, ymin = 2, ymax = 4) और (xmin = 6, xmax = 8, ymin = 3, ymax = 4) पर समाप्त होता है। खोज पेड़

(0, 8, 4) (a, c, 3) 

मुझे लगता है कि इस बिंदु से चीजें स्पष्ट होनी चाहिए।degeneracies से निपटने पर

abc 
0+-----------+ 
1|   | 
2+--+--+-----| 
3| |R |-+-+-| 
4+--+--+-|S| | 
5|  | | | 
6+-+--+--+ | | 
7| |T +--+-+-+ 
8+-+--+------+ 
9+-----------+ 

एक नोट:: यहाँ समाप्त rectangulation है के साथ शीर्ष घटनाओं से पहले डाल नीचे घटनाओं में एक ही y- निर्देशांक, और शून्य क्षेत्र के साथ आयतों को दबाने। सामान्य रूप से अभी भी "अनावश्यक" आयताकार होंगे, जो एक अधिक परिष्कृत घटना प्रोसेसर से बच सकता है (एक ही समय में किसी दिए गए वाई-समन्वय पर सभी घटनाओं को संभालने से)।