Title:	A simple and efficient algorithm for sorting the intersection points between a Jordan curve and a line
Authors:	Sojka, Eduard
Citation:	Journal of WSCG. 1997, vol. 5, no. 1-3.
Issue Date:	1997
Publisher:	Václav Skala - UNION Agency
Document type:	č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)
Keywords:	výpočetní geometrie;Jordanovo třídění;výstřižek polygonu
Keywords in different language:	computational geometry;Jordan sorting;polygon clipping
Abstract in different language:	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.
Rights:	© Václav Skala - UNION Agency
Appears in Collections:	Volume 5, number 1-3 (1997)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.