Motiverade av problemet med att märka kartor, undersöker vi problemet med att beräkna en stor icke-intersekterande delmängd i en uppsättning n rektanglar i planet. Våra resultat är som följer. I O(n log n) tid, kan vi nda en O(log n)-faktor approximation av den maximala delmängd i en uppsättning av n godtyckliga axel-parallell rektanglar i planet. Om alla rektanglar har enhet höjd, kan vi nda en 2- approximation i O(n log n) tid. Utöka detta resultat, vi får en (1 + 1 k ) - tillnärmning i tiden O (n log n + n 2k?1 ) tid, för alla heltal k 1.
I två dimensioner, Agarwal et al. REF presenterade en statisk algoritm som beräknar O(log n) approximation av maximal IS för n godtycklig axel-parallell rektangel i tid O(n log n).
Label Placement by Maximum Independent Set in Rectangles
{'venue': 'Computational Geometry: Theory and Applications', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}