alasdair
Thanks for the comments. i agree with most of your comments.
>One thing that you really ought to note is that your CSC method works in
>exponential time.
thats kinda obvious, isn't it? as i quote in the conclusion the
computational complexity (in the worst case and theoretical limit) is
indeed of polynomial order and the order depends upon the number of optimal
observers you are trying to find. In addition, you really don't have to
search for all possible combinations anyway. I have actually implemented a
random-search method which produced the optimal observers for the shape in
paper (with about 4000 obseververs) in a matter of seconds. I didn't have
to test the entire possible set. I am "casually" optimistic that with a
careful selection of the number and locations of potential observers, one
can reduce the computational time of even an "exponential" problem to quite
reasonable levels. I am looking in the CS literature to find good
heuristics for set stuff at the same time thinking of suitable observer
placement ideas.
Thanks for the paper reference. I will make sure to look into it
>One point about these methods is that they do not reduce the Art Gallery
>Problem to a set problem, as the grid resolution influences what can see
>what. Even with the grid resolution and wall resolution set, the offset
>may make a difference to the number of guards (qu.: is the problem of
>finding the optimal offset NP-hard if these resolutions are set?)
I would like to think so. One we have the established the adjacency sets of
potential observers, one only needs to perform set unions and inequality
tests to produce the optimal observers i.e. we can forget the topology of
the space all together and I think that's where the real potential of the
solutions lie i.e. they only depend upon the number of potential observers
and not upon the topological type and size of art gallery. This means, that
one can now solve real examples e.g. 3D spaces (implemented in the next
release of Isovist Analyst Extension), arbitrary topology etc.
cheers,
sanjay.
|