🚀 go-pugleaf

In article <1992Nov17.150028.9905@coe.montana.edu>, wombat@cs.montana.edu (Izurieta) writes:
> 
> 	I have been reading a few papers in segmentation of environments
> into regions.  Apparently, this is done by humans to create cognitive
> maps of some areas.  These regions in turn, form part of a hierarchy.
> 
> 	Here is my question,  What are the advantages of using a hierarchy
> to subdivide an environment?  Are there any computational advantages?

(I posted in order to prevent tens of messages being sent to Izurieta).

There's certainly a search-time advantage relative to searching a list.
If the tree has N leaves and the list N elements, a branching factor of
2 would get you from the root to a leaf in log-base-2-of N steps, while
it may take you a full N steps for an unsorted list.

But depending on whether you interpret the nonterminal nodes in the tree
as representing something essential or not, binary trees require more
space (2N - 1) than lists (N).

You might want to look at Aho, Hopcroft, and Ullman, _Data Structures
and Algorithms_.

	-dp-