Back to search

Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science

Covering points with axis parallel lines

Abstract

dc:description.abstract

In this thesis, 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 integral solution to the problem. We also propose a combinatorial algorithm by using the branch and bound technique which gives an optimal integral solution to the point cover problem. Later we implemented another approximation algorithm based on primal-dual and iterative rounding approaches. Finally we show the comparative analysis between the two iterative rounding algorithms.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Jahan, Kawsar
  • University of Lethbridge. Faculty of Arts and Science
Advisors dc:contributor.supervisor
  • Gaur, Daya
  • Benkoczi, Robert

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_CA

Identifiers

dc:identifier.*
Identifier
hdl:10133/4414

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jahan, Kawsar; University of Lethbridge. Faculty of Arts and Science. Covering points with axis parallel lines. Masters thesis, Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science, 2015. https://hdl.handle.net/10133/4414