Abstrakt. I denna not presenterar vi en enkel kombinatorisk faktor 6 algoritm för att approximera den minsta slå uppsättningen av en familj R = {R 1,. ., R n } av axel-parallell rektanglar i planet sådan att det finns en axel-monoton kurva γ som skär varje rektangel i familjen. Kvaliteten på slaguppsättningen visas genom att jämföra den med storleken på en förpackning (uppsättning av parvis icke-skärande rektanglar) som är konstruerad längs, därför får vi också en faktor 6 approximation för maximal förpackning av R. I de fall där axel-monotonkurvan γ skär samma sida (t.ex. den nedre sidan) av varje rektangel i familjen approximationsfaktorn för slå uppsättning och förpackning är 3.
Chepoi och Felsner REF föreslog 6-approximation polynom tid algoritm för fallet med axel-parallell rektanglar skärs av en axel-monoton Lagrangian kurva.
Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
{'venue': 'Comput. Geom.', 'journal': 'Comput. Geom.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}