Spot on Alastair!
I think I will probably have to eat my shoe for claiming this before proving
it in a paper but I believe that I have an O(n^8) (or perhaps the foundation
of an even better; n = number of nodes) exhaustive search algorithm that
solves the AGP equivalent.
The computational load depends upon the mutual ovelap of visual cover
amongst observers. Its essentially about carefully constructing
configurations (a set of observers) of possible optimal observers. Unlike my
previous attempts (back in 2004 i think), its not combinatorial since only
an O(n^2) number of relevant (based on intervisibility relationships)
configurations are evaluated and there are upper/lower bounds to constrain
the configuration size i.e. there is a clear convergence and finite pattern.
It is non-optimised that means it may be possible to solve the core
algorithm in lesser times using software and hardware optimisations. Its a
sort of a greedy search but not blind. It also probably relates to
branch-and-bound type heuristics although this is an exact solution.
The solution is indepdent of the shape of the open space i.e. you could use
it for topologically arbitrary open space. Hence, my focus on the topology
of the visibility graph and not the open space that generates the graph.
I am bouncing around the idea amongst various researchers and fixing
presentation (english, style etc.) issues before having a second go at
publishing it. Proving the case for a visibility graphs of various range of
mutual covers has been an issue so far.
I don't think that its difficult at all to construct a software that can
generate such topologically arbitrary visibility graphs i.e. with varying
degree of mutual overlap of isovists amongst the observers. There is clearly
a finite range of possible mutual overlaps (boolean relationships,
undirected, and in an euclidean open space). I just thought someone may have
already looked into it thus would save me from trying to prove one more
thing in the paper - you know how unreasonable some reviewers can be :-)
|