Search ETDs:
A Geometric Tiling Algorithm for Approximating Minimal Covering Sets
Martinez, Adam P.

2011, Master of Science, University of Akron, Applied Mathematics.
The cover generation problem is relevant to the problem of creating large-scale wire-
less sensor networks. Wireless sensor networks have short-ranged sensor nodes that
may not be capable of transmitting to base station. Quickly and efficiently placing
relay nodes allows the sensors to save on battery power and transmit information
back to the base station via the relay nodes. Placing a minimal cover of relays is
at least an NP-hard problem. We present a geometric tiling algorithm to construct
an approximation to a minimal covering set in O(n) time. The algorithm fills the
target region with a triangular grid of relays and then culls unnecessary points from
the grid. A brief analysis of the algorithm is presented and a comparison to another
cover-generation algorithm is performed.
Timothy Norfolk, Dr. (Advisor)
Curtis Clemons, Dr. (Committee Member)
Kathy Liszka, Dr. (Committee Member)
36 p.

Recommended Citations

Hide/Show APA Citation

Martinez, A. (2011). A Geometric Tiling Algorithm for Approximating Minimal Covering Sets. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Martinez, Adam. "A Geometric Tiling Algorithm for Approximating Minimal Covering Sets." Electronic Thesis or Dissertation. University of Akron, 2011. OhioLINK Electronic Theses and Dissertations Center. 02 Aug 2015.

Hide/Show Chicago Citation

Martinez, Adam "A Geometric Tiling Algorithm for Approximating Minimal Covering Sets." Electronic Thesis or Dissertation. University of Akron, 2011. https://etd.ohiolink.edu/

Files

akron1321028719.pdf (172.03 KB) View|Download