Hardware-efficient schemes for logarithmic approximation and binary search with application to visibility graph construction

Visibility graphs constitute a useful data structure for environment representation in the context of robot path planning. A central element in the construction of the basic visibility graph and its variants is tangent determination. This letter presents new schemes and hardware designs for key elements in tangent construction and identification of obstructed tangents. The designs have been synthesized using Synopsys Design Compiler 2001.08-SP1, and results show they are appropriate for development of a cost-effective and efficient visibility graph generation system.