Low Memory Local Geometric Routing with Guaranteed Delivery in Monotone Subdivisions

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

D'Angelo, Anthony Mark

Date: 

2016

Abstract: 

Recently, 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 \log_2{(d + 1)}\rceil$ bits of extra memory per message, where the $d$ possible edge directions are fixed to $d/2$ different slopes.

Subject: 

Computer Science

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Computer Science: 
M.C.S.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).