Covering and packing of triangles intersecting a straight line

Abstract

We study four geometric optimization problems:�set cover,�hitting set,�piercing set, and�independent set�with�right-triangles�(a triangle is a right-triangle whose base is parallel to the�-axis, perpendicular is parallel to the�-axis, and the slope of the hypotenuse is�). The input triangles are constrained to be intersecting a�straight line. The straight line can either be a�horizontal�or an�inclined�line (a line whose slope is�). A right-triangle is said to be a�-right-triangle, if the length of both its base and perpendicular is�. For 1-right-triangles�where the triangles intersect an inclined line, we prove that the set cover and hitting set problems are�-hard, whereas the piercing set and independent set problems are in�. The same results hold for 1-right-triangles�where the triangles are intersecting a horizontal line instead of an inclined line. We prove that the piercing set and independent set problems with right-triangles�intersecting an inclined line are�-hard. Finally, we give an��time exact algorithm for the independent set problem with�-right-triangles�intersecting a straight line such that��takes more than one value from�, for some integer�. We also present�-time dynamic programming algorithms for the independent set problem with 1-right-triangles�where the triangles intersect a horizontal line and an inclined line.