Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Infimaximal frames: a technique for making lines look like segments

Seel, Michael and Mehlhorn, Kurt

MPI-I-2000-1-005. December 2000, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Many geometric algorithms that are usually formulated for points and
segments generalize easily to inputs also containing rays and lines.
The sweep algorithm for segment intersection is a prototypical
example. Implementations of such algorithms do, in general, not
extend easily. For example, segment endpoints cause events in sweep
line algorithms, but lines have no endpoints. We describe a general
technique, which we call infimaximal frames, for extending
implementations to inputs also containing rays and lines. The
technique can also be used to extend implementations of planar
subdivisions to subdivisions with many unbounded faces. We have used
the technique successfully in generalizing a sweep algorithm designed
for segments to rays and lines and also in an implementation of planar
Nef polyhedra.

Our implementation is based on concepts of generic programming in C++
and the geometric data types provided by the C++ Computational
Geometry Algorithms Library (CGAL).
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2000-1-005.psMPI-I-2000-1-005.pdf158 KBytes; 143 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Seel, Michael and Mehlhorn, Kurt},
  TITLE = {Infimaximal frames: a technique for making lines look like segments},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2000-1-005},
  MONTH = {December},
  YEAR = {2000},
  ISSN = {0946-011X},