| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju


1 - 4 / 4
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
Polygon trapezoidation by sets of open trapezoids
Borut Žalik, Anton Jezernik, Krista Rizman Žalik, 2003, izvirni znanstveni članek

Opis: A new efficient algorithm is described for the simple trapezoidation of polygons based on a sweep-line paradigm. As the sweep-line glides over the plane, a set of so-called open trapezoids is generated and maintained. It is shown that a boundary case (more polygon vertices are located on the sweep-line) can be solved safely and does not slow down the algorithm. If desired, the polygon holes can be trapezoidated simultaneously. This proposed algorithm when compared with the fastest known algorithm developed by Seidel resulted in more efficiency for different classes of polygons.
Ključne besede: polygon, polygon decomposition, trapezoidation, computational geometry
Objavljeno v DKUM: 01.06.2012; Ogledov: 1964; Prenosov: 128
URL Povezava na celotno besedilo

Acceleration of sweep-line technique by employing smart quicksort
David Podgorelec, Gregor Klajnšek, 2005, izvirni znanstveni članek

Opis: Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm 'vertex sort'. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertexsort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (inlinear time) than random cases. We have named the combined algorithm 'smartquicksort' because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm.
Ključne besede: computational geometry, quicksort, smart quicksort, sweep-line, smart quicksort, polygon triangualation, vertex sort
Objavljeno v DKUM: 01.06.2012; Ogledov: 1995; Prenosov: 89
URL Povezava na celotno besedilo

An almost distribution-independent incremental Delaunay triangulation algorithm
Mirko Zadravec, Borut Žalik, 2005, izvirni znanstveni članek

Opis: This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1-3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.
Ključne besede: Delaunay triangulation, incremental algorithm, computational geometry, skip list, hash table
Objavljeno v DKUM: 01.06.2012; Ogledov: 2405; Prenosov: 104
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.55 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici