An Efficient Algorithm to Construct Reduced Visibility Graph and Its FPGA Implementation

V
VLSID
2004
17th International Conference on VLSI Design
Abstract - An Efficient Algorithm to Construct Reduced Visibility Graph and Its FPGA Implementation

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by T. K. Priya Articles by K. Sridharan

17th International Conference on VLSI Design

Mumbai, India

January 05-January 09

ISBN: 0-7695-2072-3

	ASCII Text	x
	T. K. Priya, K. Sridharan, "An Efficient Algorithm to Construct Reduced Visibility Graph and Its FPGA Implementation," VLSI Design, International Conference on, pp. 1057, 17th International Conference on VLSI Design, 2004.

	BibTex	x
	@article{ 10.1109/ICVD.2004.1261069, author = {T. K. Priya and K. Sridharan}, title = {An Efficient Algorithm to Construct Reduced Visibility Graph and Its FPGA Implementation}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {2004}, issn = {1063-9667}, pages = {1057}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.2004.1261069}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - An Efficient Algorithm to Construct Reduced Visibility Graph and Its FPGA Implementation SN - 1063-9667 SP EP A1 - T. K. Priya, A1 - K. Sridharan, PY - 2004 KW - Reduced Visibility Graph KW - Binary Search KW - Parallel Algorithm and Architecture KW - FPGA Implementation VL - 0 JA - VLSI Design, International Conference on ER -

T. K. Priya, Indian Institute of Technology Madras, Chennai

K. Sridharan, Indian Institute of Technology Madras, Chennai

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICVD.2004.1261069

An important geometric structure used in robotic path planning and computer graphics is the visibility graph. In this paper, we present a new parallel algorithm to construct the reduced visibility graph that is appropriate for finding shortest paths in a convex polygonal environment. A key feature of the algorithm is that it supports easy mapping to hardware. The computational complexity is O(p²+log((n/p)²)) where p is the number of objects and n is the total number of vertices. An efficient FPGA implementation of the algorithm is presented. The design operates at approximately 48 Mhz. Further, the implementation for an environment with roughly 60 vertices requires 90% of an SCV3200E.

Index Terms:

Reduced Visibility Graph, Binary Search, Parallel Algorithm and Architecture, FPGA Implementation

Citation:

T. K. Priya, K. Sridharan, "An Efficient Algorithm to Construct Reduced Visibility Graph and Its FPGA Implementation," vlsid, pp.1057, 17th International Conference on VLSI Design, 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.