BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR86-131
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: The Pairwise Intersection Problem for Monotone Polygons
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Levine, David B.
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1986
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR86-131.pdf
ABSTRACT::
	Geometric intersection problems arise in a number of areas of
computer science including graphics and VLSI design rule checking.
Previous work has concentrated on solving the pairwise intersection
problem for line segments and iso-oriented rectangles.  This thesis
extends that work by presenting efficient algorithms to solve the
pairwise intersection problem for monotone polygons.  For general
segments, the problem has been solved in O(N+I)*logN) time using a
sweeping line technique, where N is the number of segments and I is
the number of intersections reported.  We combine this technique with
approaches taken to solve the iso-oriented rectangle problem to yield
an algorithm which solves the pairwise intersection problem for
monotone polygons in the same asymptotic time.  In addition, there are
certain classes of line segments for which the pairwise intersection
problem may be solved in O(N*logN + I) time, the best possible.  We
generalize each such class of line segments to a class of polygons and
present algorithms to solve the associated polygon problem.  Finally,
we discuss the impacts which possible improvements to the line segment
problem would have on our results.
END:: ncstrl.dartmouthcs//TR86-131