Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Accelerating of line of sight analysis algorithms with parallel programming
Download
index.pdf
Date
2017
Author
Yılmaz, Gökhan
Metadata
Show full item record
Item Usage Stats
220
views
107
downloads
Cite This
Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of sight analysis. The purpose of this research is to develop parallel adaptations of these particular algorithms by making use of the capabilities of a modern Graphics Processing Unit (GPU) and to evaluate these adaptations in terms of performance and memory usage. By analyzing which algorithm is more suitable to be implemented on the GPU, the algorithm that will provide the most appropriate and quick solution to the probing problem can be determined. In this research, Van Kreveld's algorithm, which is basically a sequential algorithm, was developed partly in parallel, and the speed-up was 1.5x compared to the sequential version of the algorithm. Speed-up rates increase up to 10.5x for R2 and 160x for R3 algorithms, respectively. The results can be used to combine CPU / GPU approaches in order to perform hybrid or full parallelization of Van Kreveld’s Algorithm on the GPU. The results presented in the thesis will serve as a guide for the selection of the appropriate algorithm by evaluating the strengths and weaknesses of different algorithms.
Subject Keywords
Geographic information systems.
,
Parallel programming (Computer science).
URI
http://etd.lib.metu.edu.tr/upload/12620986/index.pdf
https://hdl.handle.net/11511/26798
Collections
Graduate School of Informatics, Thesis
Suggestions
OpenMETU
Core
Acceleration of line of sight analysis algorithms with parallel programming
Yılmaz, Gökhan; Sürer, Elif; Temizel, Alptekin (null; 2017-11-23)
Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of si...
ASSESSMENT OF RPIM SHAPE PARAMETERS FOR SOLUTION ACCURACY OF 2D GEOMETRICALLY NONLINEAR PROBLEMS
BOZKURT, ÖMER YAVUZ; KANBER, BAHATTİN; Aşık, Mehmet Zülfü (World Scientific Pub Co Pte Lt, 2013-06-01)
This study discussed the effects of shape parameters on the radial point interpolation method (RPIM) accuracy in 2D geometrically nonlinear problems. Four finite deformation problems with compressible Neo-Hookean material are numerically solved with the RPIM algorithm using the multi-quadric (MQ) radial basis function. Both regular and irregular node distributions are used. Their displacements and Cauchy stresses are compared for different values of shape parameters and monomial basis. It is found that the ...
Parallel implementation of the accelerated BEM approach for EMSI of the human brain
ATASEVEN, YOLDAŞ; Akalin-Acar, Z.; Acar, C. E.; Gençer, Nevzat Güneri (Springer Science and Business Media LLC, 2008-07-01)
Boundary element method (BEM) is one of the numerical methods which is commonly used to solve the forward problem (FP) of electro-magnetic source imaging with realistic head geometries. Application of BEM generates large systems of linear equations with dense matrices. Generation and solution of these matrix equations are time and memory consuming. This study presents a relatively cheap and effective solution for parallel implementation of the BEM to reduce the processing times to clinically acceptable valu...
Classification of remotely sensed data by using 2D local discriminant bases
Tekinay, Çağrı; Çetin, Yasemin; Department of Information Systems (2009)
In this thesis, 2D Local Discriminant Bases (LDB) algorithm is used to 2D search structure to classify remotely sensed data. 2D Linear Discriminant Analysis (LDA) method is converted into an M-ary classifier by combining majority voting principle and linear distance parameters. The feature extraction algorithm extracts the relevant features by removing the irrelevant ones and/or combining the ones which do not represent supplemental information on their own. The algorithm is implemented on a remotely sensed...
Development of free/libre and open source spatial data analysis system fully coupled with geographic information system
Kepoğlu, Volkan Osman; Düzgün, H. Şebnem; Department of Geodetic and Geographical Information Technologies (2011)
Spatial Data Analysis (SDA) is relatively narrower and constitutes one of the areas of Spatial Analysis. Geographic Information System (GIS) offers a potentially valuable platform for supporting SDA techniques. Integration of SDA with GIS helps SDA to benefit from the data input, storage, retrieval, data manipulation and display capabilities of GIS. Also, GIS can benefit from SDA techniques in which the integration of these techniques can increase the analysis capabilities of GIS. This integration serves fo...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
G. Yılmaz, “Accelerating of line of sight analysis algorithms with parallel programming,” M.S. - Master of Science, Middle East Technical University, 2017.
