2013/05/20 by Jean Souviron, Souviron, Jean
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Code (set theory) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #FOS: Computer and information sciences #Focus (optics) #Intersection (aeronautics) #Line (geometry) #Mathematics #Polygon (computer graphics) #Set (abstract data type) #Simple (philosophy) #Software #Time complexity #cs.CG
paper · pdf · doi:10.48550/arxiv.1305.4573
15 pages, 9 figures. Added 1 figure in Section 2.5 plus comments on expected value of exponent in abstract and body of paper
openalex publication_date 2013/05/20 · arxiv created 2013/05/27 · arxiv updated 2013/05/28 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
While well-known methods to list the intersections of either a list of segments or a complex polygon aim at achieving optimal time-complexity they often do so at the cost of memory comsumption and complex code. Real-life software optimisation however lies in optimising at the same time speed and memory usage as well as keeping code simple. This paper first presents some thoughts on the available algorithms in terms of memory usage leading to a very simple scan-line-based algorithm aiming at answering that challenge. Although sub-optimal in terms of speed it is optimal if both speed and memory space are taken together and is very easy to implement. For N segments and k intersections it uses only N additional integers and lists the intersections in O(N1.26) or corrects them in O((N+k) N0.26) at most in average, with a high probability of a much lower exponent around 0.16 and even as low as 0.1. It is therefore well adapted for inclusion in larger software and seems like a good compromise. Worst-case is in O(N2). Then the paper will focus on differences between available methods and the brute-force algorithm and a solution is proposed. Although sub-optimal its applications could mainly be to answer in a fast way a number of scattered unrelated intersection queries using minimal complexity and additional resources.