All possible convex hull (i.e. the minimum area convex polygon containing the planar set) algorithms ever published in scientific press have been analysed in this work. Two new convex hull algorithms created by myself have been presented. The running time of analysed algorithms has been surveyed. Three most popular algorithms (Graham Scan, Jarvis March and Quickhull), the oldest algorithm (Brute Force) as well as the both new ones have been implemented. Efficiency experiments have been carried out with them. The algorithms created by me achieved the best results. In order to raise the efficiency of all the algorithms I suggested a priori filtration of points, which decreases the amount of the original points by almost 50% and, consequently, the speed of algorithms is increased. The major part of this master work will be published in the magazine “Technological and economic development of economy”. Besides, the report of this work has been made in the conference of Lithuanian young scientists, called “Operation analysis and application”.
| Identifer | oai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2006~D_20060619_121730-70046 |
| Date | 19 June 2006 |
| Creators | Vyšniauskaitė, Laura |
| Contributors | Šaltenis, Vydūnas, Račienė, Jurga, Kazlauskas, Kazys, Dzemyda, Gintautas, Lipeikienė, Joana, Melničenko, Grigorijus, Vilnius Pedagogical University |
| Publisher | Lithuanian Academic Libraries Network (LABT), Vilnius Pedagogical University |
| Source Sets | Lithuanian ETD submission system |
| Language | Lithuanian |
| Detected Language | English |
| Type | Master thesis |
| Format | application/pdf |
| Source | http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2006~D_20060619_121730-70046 |
| Rights | Unrestricted |
Page generated in 0.0028 seconds