Approximability of covering cells with line segments

Paz Carmi, Anil Maheshwari, Saeed Mehrabi, Luís Fernando Schultz, Xavier da Silveira

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be NP-hard, even if the line segments in S are axis-parallel, and it remains NP-hard when the goal is cover the "rectangular" cells (i.e., cells that are defined by exactly four axis-parallel line segments). In this paper, we consider the approximability of the problem. We first give a PTAS for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is APX-hard. We also consider the parameterized complexity of the problem and prove that the problem is FPT when parameterized by the size of an optimal solution. Our FPT algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. [9] in which the goal is to cover the "rectangular" cells.

اللغة الأصليةإنجليزيّة أمريكيّة
عنوان منشور المضيفCombinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings
المحررونAlexander Zelikovsky, Donghyun Kim, R.N. Uma
ناشرSpringer Verlag
الصفحات436-448
عدد الصفحات13
رقم المعيار الدولي للكتب (المطبوع)9783030046507
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2018
الحدث12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018 - Atlanta, الولايات المتّحدة
المدة: ١٥ ديسمبر ٢٠١٨١٧ ديسمبر ٢٠١٨

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت11346 LNCS

!!Conference

!!Conference12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018
الدولة/الإقليمالولايات المتّحدة
المدينةAtlanta
المدة١٥/١٢/١٨١٧/١٢/١٨

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Approximability of covering cells with line segments'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا