Midpoint routing algorithms for Delaunay triangulations

Weisheng Si; Albert Y. Zomaya

doi:10.1109/IPDPS.2010.5470471

Midpoint routing algorithms for Delaunay triangulations

Weisheng Si, Albert Y. Zomaya

School of Computer, Data & Mathematical Sciences

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

4 Citations (Scopus)

Abstract

Memoryless online routing (MOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new MOR algorithms for a class of geometric graphs called Delaunay triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. More meaningfully, the former is generalized into a set of MOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of MOR algorithms that use the direction as the reference and work for DTs. Many other existing MOR algorithms can also be covered by these two sets. Finally, the two new algorithms are evaluated and compared with other existing MOR algorithms, and the experimental results give new findings on the performances of these algorithms in average and general cases.

Original language	English
Title of host publication	Proceedings of the 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS 2010): Atlanta, Georgia, USA, 19-23 April 2010
Publisher	IEEE
Number of pages	7
ISBN (Print)	9781424464432
DOIs	https://doi.org/10.1109/IPDPS.2010.5470471
Publication status	Published - 2010
Event	IPDPS (Conference) - Duration: 19 Apr 2010 → …

Conference

Conference	IPDPS (Conference)
Period	19/04/10 → …

Access to Document

10.1109/IPDPS.2010.5470471

Cite this

@inproceedings{642ec0fc1c484ab08dd0a9e42010e41d,

title = "Midpoint routing algorithms for Delaunay triangulations",

abstract = "Memoryless online routing (MOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new MOR algorithms for a class of geometric graphs called Delaunay triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. More meaningfully, the former is generalized into a set of MOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of MOR algorithms that use the direction as the reference and work for DTs. Many other existing MOR algorithms can also be covered by these two sets. Finally, the two new algorithms are evaluated and compared with other existing MOR algorithms, and the experimental results give new findings on the performances of these algorithms in average and general cases.",

author = "Weisheng Si and Zomaya, {Albert Y.}",

year = "2010",

doi = "10.1109/IPDPS.2010.5470471",

language = "English",

isbn = "9781424464432",

booktitle = "Proceedings of the 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS 2010): Atlanta, Georgia, USA, 19-23 April 2010",

publisher = "IEEE",

note = "IPDPS (Conference) ; Conference date: 19-04-2010",

}

TY - GEN

T1 - Midpoint routing algorithms for Delaunay triangulations

AU - Si, Weisheng

AU - Zomaya, Albert Y.

PY - 2010

Y1 - 2010

N2 - Memoryless online routing (MOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new MOR algorithms for a class of geometric graphs called Delaunay triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. More meaningfully, the former is generalized into a set of MOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of MOR algorithms that use the direction as the reference and work for DTs. Many other existing MOR algorithms can also be covered by these two sets. Finally, the two new algorithms are evaluated and compared with other existing MOR algorithms, and the experimental results give new findings on the performances of these algorithms in average and general cases.

AB - Memoryless online routing (MOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new MOR algorithms for a class of geometric graphs called Delaunay triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. More meaningfully, the former is generalized into a set of MOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of MOR algorithms that use the direction as the reference and work for DTs. Many other existing MOR algorithms can also be covered by these two sets. Finally, the two new algorithms are evaluated and compared with other existing MOR algorithms, and the experimental results give new findings on the performances of these algorithms in average and general cases.

UR - http://handle.uws.edu.au:8081/1959.7/562572

UR - http://www.ipdps.org/ipdps2010/2010_advance_program.html

U2 - 10.1109/IPDPS.2010.5470471

DO - 10.1109/IPDPS.2010.5470471

M3 - Conference Paper

SN - 9781424464432

BT - Proceedings of the 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS 2010): Atlanta, Georgia, USA, 19-23 April 2010

PB - IEEE

T2 - IPDPS (Conference)

Y2 - 19 April 2010

ER -

Midpoint routing algorithms for Delaunay triangulations

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this