MPI-INF/SWS Research Reports 1991-2021

# MPI-I-94-162

## On the parallel complexity of degree sequence problems

### Arikati, Srinivasa R.

#### November 1994, 12 pages.

.
##### Status: available - back from printing

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.

• MPI-I-94-162.pdf
• Attachement: MPI-I-94-162.ps.gz (59 KBytes); MPI-I-94-162.pdf (190 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-162

BibTeX
@TECHREPORT{Arikati94MPII94-162,
AUTHOR = {Arikati, Srinivasa R.},
TITLE = {On the parallel complexity of degree sequence problems},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-162},
MONTH = {November},
YEAR = {1994},
ISSN = {0946-011X},
}