Abstract:
The problems posed in the paper are those of computing multiple geometric intersections in applications such as analysis of LSI circuits, computer graphics, etc. Algorithms are proposed with estimates proportional to $N\lg N+K$ and $N\lg N$ for enumeration and calculation, respectively, of the number of intersection points in edges of a specific digraph on a plane, $N$ being the number of edges and $K$, of intersection points. Asymptotical optimality of the; proposed algorithms is proved.