MPI-I-2000-1-005
Infimaximal frames: a technique for making lines look like segments
Seel, Michael and Mehlhorn, Kurt
December 2000, 16 pages.
.
Status: available - back from printing
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).
-
- Attachement: MPI-I-2000-1-005.ps (158 KBytes); 89024854.pdf (143 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2000-1-005
BibTeX
@TECHREPORT{SeelMehlhorn00,
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},
}