SORU
7 Mayıs 2011, CUMARTESİ


Algoritma dikdörtgenler bir dizi karşılamak için en az dikdörtgenler bulmak için

Dikdörtgenler ve "ben orijinal olarak aynı alanı tarif etmek için dikdörtgenler, en az ayarlayın. azaltmak istiyorum var Mümkünse, aynı zamanda hızlı olmak istiyorum, ama dikdörtgenler sayısını mümkün olduğunca düşük almak daha çok ilgiliyim. Çoğu zaman çalışan bir yaklaşım var artık.

Şu anda, üst-sol en dikdörtgenin başlar ve eğer bir dikdörtgen tutarken doğru ve aşağı genişletmek miyim diye. Artık genişletin ve tüm kesişen dikdörtgenler kaldırmak bölünmüş ve genişletilmiş dikdörtgen geri listesine ekle Bu kadar. Daha sonra sol üst en sonraki dikdörtgen ile, başlıyorum. Ama bazı durumlarda işe yaramıyor. Örneğin: enter image description here

Üç dikdörtgenler bu set ile, doğru çözüm bu gibi iki dikdörtgenler ile sonuna kadar: enter image description here

Ancak, bu durumda, benim algoritma mavi dikdörtgen işleme başlar. Bu aşağıya doğru genişletin ve sarı dikdörtgen (doğru) böler. Ama sonra sarı dikdörtgenin kalan, aşağıya doğru genişleyen yerine işlendiğinde, ilk genişler ve daha önce bölünmüş kapalı olan kısmını geri alıyor. Son bir dikdörtgen işlenir ve dikdörtgenler özgün kümesi geriye doğru ya da aşağı doğru genişletin. Önce ve sonra genişletmek için algoritma çimdik olabilir. Bu durumda düzeltmek istiyorum, ama saygısız olduğunu benzer bir senaryoda, aynı sorunlara yol açar.

Herhangi bir yardım için şimdiden teşekkür ederim.

Düzenleme:Sadece netleştirmek için, dikdörtgenler özgün kümesi bağlı olması gerekmez ve örtüşme yok. Ve eğer dikdörtgen bir alt bağlıysa, onları tamamen kapsayan çokgen delik olabilir.

CEVAP
9 Temmuz 2011, CUMARTESİ


Sorunuzun Başlığı rağmen, aslında en az arıyorsun sanırımdiseksiyondörtgen çokgen dikdörtgen içine. (Jason bağlantıları minimum üzeresinizkapsarfarklı bir sorun hangi oldukça dikdörtgenler, tarafından.)

David Eppstein 2010 anket yazısında Graph-Theoretic Solutions to Computational Geometry Problems, this answer on mathoverflow.net güzel bir özet verir 3. bölümde bu sorunu ele almaktadır:

Fikrini eksenine paralel çapraz bitiş noktaları olarak iki içbükey köşeler var ayrık sayısını bulmak, bu bölünmüş boyunca, ve kalan her içbükey köşe için bir daha bölünmüş form. Ayrık sayısı eksenine paralel çapraz bulmak için, çapraz kesişme grafik şeklinde; bu grafik maksimum bağımsız seti grafik eşleştirme teknikleri ile polinom zaman bulunabilir yani iki taraflı.

İşte benim takdire kısa ve öz bu açıklama, Eppstein bu makale Şekil 2 kullanılarak parlak. Dörtgen çokgen, muhtemelen delik olduğunu varsayalım.

enter image description here

Çokgen dikdörtgen civarında iken, içbükey köşeleri her diseksiyonu bir kenar ile bir araya geldi olacak. Biz yaniminimumeğer mümkün olduğunca bu kenarlar birçok çift görev olduğu, diğer bir deyişle, içbükey iki İnternet'e diseksiyonu köşeler.

O zaman iki içbükey tepe noktaları arasında eksenine paralel bütün açıları çizelim (diagonal of a polygon bir çizgi olmayan bitişik iki köşe bağlanıyor). Mümkün olduğunca bu satırların kullanımına diseksiyonu istediğiniz gidiyoruz.

enter image description here

Çizgi parçaları bir dizi intersection graph her çizgi parçası için bir düğüm ve kenar çizgileri çapraz eğer iki düğüm arasına katıldı. İşte eksen paralel çapraz kesişim grafik:

enter image description here

bipartite bir kısmı dikey çapraz ile, diğer kısmı yatay denir. Şimdi, mümkün olduğunca çapraz gibi birçok almak için bilgisayar yok sürece istiyoruz. Bu kesişme grafik maximum independent set bulma karşılık gelir.

Bulma maksimum bağımsız küme bir genel grafik bir NP-tam problem, ama bu özel durumda bir iki taraflı grafik, König's theorem gösteren bu eşdeğer sorunun bulma en fazla eşleşen, çözülecek polinom zaman, örneğin tarafından Hopcroft–Karp algorithm. İşte en fazla eşleşen:

enter image description here

Ve burada minimum vertex cover (kırmızı) karşılık gelen maksimum bağımsız set (yeşil)

enter image description here

Diseksiyon sorun haline geri çevirmek, bu diseksiyonu ekseni paralel beş çapraz kullanabileceğimiz anlamına gelir:

enter image description here

Son olarak, kalan her içbükey köşe bir kesim diseksiyonu tamamlamak için:

enter image description here

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • FPSRussia

    FPSRussia

    19 NİSAN 2010
  • Rachel Talbott

    Rachel Talbo

    26 Ocak 2011
  • thetrollska

    thetrollska

    2 EKİM 2009