Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 4 of 4 for “"axis parallel lines"”.
-
Covering points with axis parallel lines
… we study the problem of covering points with axis parallel lines. We named it as the point cover problem. Given a set of the n points in d dimensional space, the goal is to cover the points with minimum number of axis parallel lines. We use the iterative rounding approach which gives an …
-
Point cover problem in 3D
… of covering points with minimum number of axis-parallel lines in three dimensional space which is an NP-complete problem. We introduce Lagrangian based algorithms to approximate the point cover problem. We study the Lift-and-Project relaxation of the standard IP to obtain lower bounds. This …
-
Node-Link, Obstacle, and Intersection Representations of Graphs and Hypergraphs
… vertices are represented by y-monotone curves or axis-parallel lines. Our primary focus is determining whether a given graph or hypergraph admits a desired representation. We analyze the complexity of most of these problems and provide explicit constructions for specific graph classes.
-
On Covering Points with Conics and Strips in the Plane
… points in the plane, find the minimum number of lines to cover them. In Euclidean space Rm, this problem is known as Hyperplane Cover, where lines are replaced by affine hyperplanes bounded by dimension d. Line cover is NP-hard, so is its hyperplane analogue. Our thesis focuses on few extensions …