Název:	A simple and efficient algorithm for sorting the intersection points between a Jordan curve and a line
Autoři:	Sojka, Eduard
Citace zdrojového dokumentu:	Journal of WSCG. 1997, vol. 5, no. 1-3.
Datum vydání:	1997
Nakladatel:	Václav Skala - UNION Agency
Typ dokumentu:	článek article
URI:	http://hdl.handle.net/11025/15886 http://wscg.zcu.cz/wscg1997/wscg97.htm
ISSN:	1213-6972 (print) 1213-6980 (CD-ROM) 1213-6964 (online)
Klíčová slova:	výpočetní geometrie;Jordanovo třídění;výstřižek polygonu
Klíčová slova v dalším jazyce:	computational geometry;Jordan sorting;polygon clipping
Abstrakt v dalším jazyce:	In this paper, we focus on the Jordan sorting problem: Given N intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve. The task is to sort these points into the order in which they occur along the x-axis. Contrary to general sorting whose solution (in the algebraic decision-tree model of computation) requires θ(N log N) time in the worst case, the Jordan sorting problem can be solved in θ(N) time. The linear worst-case time algorithms for Jordan sorting were proposed by Hoffman et al., and by Fung et al. Unfortunately, both these algorithms are rather complicated, which makes them difficult to use in practice. In this paper, we propose and analyse a simple algorithm for Jordan sorting. Although the worst-case time complexity of this algorithm is O(N log N), we show that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. We also show that for a certain class of inputs which may be of practical interest, the algorithm runs even in O(N) expected time. We believe that for many practical applications, the algorithm may be more advantageous than rather complicated worst-case time optimal algorithms. Our main result is the analysis of this otherwise rather straightforward algorithm.
Práva:	© Václav Skala - UNION Agency
Vyskytuje se v kolekcích:	Volume 5, number 1-3 (1997)

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.