Carleton University
Low Memory Local Geometric Routing with Guaranteed Delivery in Monotone Subdivisions
Abstract
dc:description.abstractRecently, deterministic geometric local routing algorithms were presented with guaranteed delivery for convex subdivisions using only one bit and for monotone subdivisions using only predecessor awareness (in "Local Routing in Convex Subdivisions", SOFSEM 2015: 140-151). We present a simple deterministic geometric local routing algorithm that guarantees delivery in monotone planar subdivisions (which include convex subdivisions) without a general position assumption. Our algorithm uses \lceil \log2{(d + 1)}\rceil bits of extra memory per message, where the $d$ possible edge directions are fixed to $d/2$ different slopes.
Degree
thesis:*- Name thesis:degree_name
- Master of Computer Science (M.C.S.)
- Level thesis:degree_level
- Master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- Carleton University
- Year dc:date.issued
- 2016
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- D'Angelo, Anthony Mark
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- Copyright © 2016 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Language dc:language.iso
- en