Help Privacy Policy Disclaimer
  Advanced SearchBrowse





On the parallel complexity of degree sequence problems


Arikati,  Srinivasa
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 190KB

Supplementary Material (public)
There is no public supplementary material available

Arikati, S.(1994). On the parallel complexity of degree sequence problems (MPI-I-1994-162). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B695-6
We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm based on the LEDA library of efficient data types and algorithms. The program computes the planar graph $G$ induced by a set $S$ of straight line segments in the plane. The nodes of $G$ are all endpoints and all proper intersection points of segments in $S$. The edges of $G$ are the maximal relatively open subsegments of segments in $S$ that contain no node of $G$. All edges are directed from left to right or upwards. The algorithm runs in time $O((n+s) log n)$ where $n$ is the number of segments and $s$ is the number of vertices of the graph $G$. The implementation uses exact arithmetic for the reliable realization of the geometric primitives and it uses floating point filters to reduce the overhead of exact arithmetic.