NP-completeness and FPT Results for Rectilinear Covering Problems

This paper discusses three rectilinear (that is, axis-parallel) covering problems in d dimensions and their variants. the first problem is the rectilinear line cover where the inputs are n points in rd and a positive integer k,and we areasked to answer if we can cover these n points with at most k lines where these lines are restricted to be axis parallel. we show that this problem has efficient fixed-parameter tractable (fpt) algorithms. the second problem is the rectilinear k-links spanning path problem where the inputs are also n points in rd and a positive integer k but here we are asked to answer if there is a piecewise linear path through these n points having at most k line-segments (links) where these line-segments are axis- parallel. we prove that this second problem is fpt under the assumption that no two line-segments share the same line. the third problem is the rectilinear hyper- plane cover problem and we are asked to cover a set of n points in d dimensions with k axis-parallel hyperplanes of d - 1 dimensions. we also demonstrate this has an fpt-algorithm. previous to the results above, only conjectures were enunciated over several years on the np-completeness of the rectilinear minimum link traveling salesman problem,the minimum link spanning path problem and the recti- linear hyperplane cover. we provide the proof that the rectilinear minimum link traveling salesman problem and the rectilinear minimum link span- ning path problem are np-complete by a reduction from the one-in-three 3-sat problem. the np-completeness of the rectilinear hyperplane cover problem is proved by a reduction from 3-sat. this suggests dealing with the intractability just discovered with fixed-parameter tractability. moreover, if we extend our problems to a finite set of orientations, our approach proves these problems remain fpt.