{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T04:30:26Z","timestamp":1648614626039},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J CIRCUIT SYST COMP"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p> The reconfigurable mesh (R-Mesh) was shown to be a very powerful model capable of extremely fast solutions to many problems. R-Mesh has a wide range of applications such as arithmetic problems, image processing and robotics. The 2D R-Mesh was shown to be able to solve the path planning problem very fast. <\/jats:p><jats:p> In this paper, we propose an algorithm to compute a collision-free path, P, between a source and a destination in an environment with the existence of obstacles. Independent of the number of obstacles, k, the proposed algorithm runs in constant time and requires O( log <jats:sup>2<\/jats:sup>N) pre-processing time where N is the size of the R-Mesh. This is in contrast to the previous work that requires O(k) time with the same pre-processing time. We then consider the quality of the generated path. We present a constant-time modification to enhance the length of the path and analyze the generated path P in terms of the number of bends in P. We derive the number of bends in P for any set of obstacles. We also derive a necessary condition for the minimum number of bends in the path P, i.e., a lower bound on the number of bends. We finally identify a class of obstacles for which the above necessary condition is sufficient as well (tight bound). <\/jats:p>","DOI":"10.1142\/s0218126615501121","type":"journal-article","created":{"date-parts":[[2015,5,22]],"date-time":"2015-05-22T03:00:25Z","timestamp":1432263625000},"page":"1550112","source":"Crossref","is-referenced-by-count":0,"title":["Constant Time Algorithm for Computing a Collision-Free Path on R-Mesh with Path Quality Analysis"],"prefix":"10.1142","volume":"24","author":[{"given":"Hatem M.","family":"El-Boghdadi","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Cairo University, Giza, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2015,8,12]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90084-M"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/12.277290"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02915447"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626495000102"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.03.002"},{"key":"rf8","first-page":"1","volume":"99","author":"Bowen C.","year":"2014","journal-title":"IEEE Trans. Automat. Sci. Eng."},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1049\/el.2013.3143"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/70.563646"},{"key":"rf15","volume":"28","author":"Wang D.","year":"1998","journal-title":"IEEE Trans. Syst., Man, Cybern."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/b100618"}],"container-title":["Journal of Circuits, Systems and Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218126615501121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:14:48Z","timestamp":1565093688000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218126615501121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,12]]},"references-count":10,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,8,12]]},"published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1142\/S0218126615501121"],"URL":"https:\/\/doi.org\/10.1142\/s0218126615501121","relation":{},"ISSN":["0218-1266","1793-6454"],"issn-type":[{"value":"0218-1266","type":"print"},{"value":"1793-6454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,12]]}}}