August – 2008 ^September

Given a geometric structure of a building (B) and the location of transmitter (T) and a receiver (R) inside B. We would like to calculate all bounded length Radio Paths between T and R. This work presents a new Radio Paths computation frame-work specially design for complex indoor prediction. The suggested new algorithm (IDRP) uses a geometric visibility graph (of B) to traverse all possible bounded paths. Such paths are needed in order to compute the signal strength of T as received at R. We have implemented a prototype version of the IDRP algorithm and performed preliminary experiment testing the radio paths over complex buildings. The main conclusion is that the new IDRP is time efficient and can compute all relevant radio paths even on relatively complex building in a fraction of a second. The suggested work is currently being implemented as part of the Israeli Short Range Consortium (ISRC), at the last part of the talk several open questions will be posted. This talk requires NO background in Radio Frequency.

Keywords: Indoor wireless communication, 3D Geometric paths, Approximating Signal Strength, Visibility Graph.

Boaz is a faculty member in the department of computer science at Ariel University Center. He received the B.Sc., M.Sc. and Ph.D. degrees in Computer Science from Ben-Gurion University, Israel. During 2004-2005 he was a post doctoral fellow at Simon Fraser University - Vancouver Canada. His main area of research is Computational Geometry and GIS algorithms, his research includes terrain simplification, layout design and simulation of wireless networks, visibility graphs, navigation, and vehicle routing problems

The following conjecture made by Gyarfas in 1973 is of interest.

For any integer k, there exists an integer g(k) such that every graph with chi(G) geq g(k) contains either a K_k or an odd hole of length at least 5.

In 1996, in a rather short and elegant proof, Scott provided a partial answer to the above conjecture. In addition, the result of Scott also provides a partial answer to another conjecture put forth by Sumner in 1981. Recently, Chudnovsky, Robertson, Seymour, and Thomas have obtained additional advancement regarding the conjecture of Gyarfas.

A discussion as to the result of Scott is offered.