All
A
I'
I
rrL
v
g
S
I
3
Ii
p
1
p
I 1,
:
I$',i,.d]'
]1,
I
1
1'
ALGORITHMS
AND
DATA
STRUCTURES
With
Applications
to
Graphics and
Geometry
JURG

p.
cm.
Includes
bibliographical
references and indexes.
ISBN 0-13-489428-6
1.
Computer
algorithms.
2.
Computer
structures (Computer
science)
3.
Computer
graphics.
1.
Hinrichs,
Klaus.
11.
Title.
QA76.9.A43N54
1993
005.1-
-
dc2O
92-4687
CIP
Acquisitions
editor:

Inc.
A
Simon
&
Schuster
Company
I=
Englewood
Cliffs, New
Jersey
07632
The
author
and
publisher
of
this
book
have used
their
best
efforts
in
preparing this
book.
These
efforts
include the
development,
research,

The author
and
publisher
shall
not
be
liable
in
any
event
for
incidental
or consequential
damages
in
connection
with, or arising out
of,
the
furnishing,
performance, or
use
of
these
programs.
All rights
reserved.
No
part
of

2
1
ISBN
0-13-489428-6
Prentice-Hall International
(UK)
Limited,
London
Prentice-Hall
of
Australia
Pty.
Limited, Sydney
Prentice-Hall Canada
Inc.,
Toronto
Prentice-Hall Hispanoamericana,
S.A.,
Mexico
Prentice-Hall
of
India Private Limited,
New
Delhi
Prentice-Hall
of
Japan,
Inc.,
Tokyo
Simon

TO
GIVEN
PRIMITIVES:
PROGRAMMING
MOTION
1.1
A
robot
car,
its
capabilities,
and
the task
to
be
performed
3
1.2
Wall-following
algorithm
described
informally
5
1.3
Algorithm
specified
in
a
high-level
language

graphics toolbox
12
A
graphics
frame
program
15
xiii
1
3
9
V
2.4
Example
of
a
graphics
routine:
Polyline
input
18
3
ALGORITHM
ANIMATION
20
3.1
Computer-driven
visualization:
Characteristics
and

LITERATURE:
SUBSTANCE
AND
FORM
32
4.1
Programming
in
the large
versus
programming
in
the
small
32
4.2 Documentation
versus
literature:
Is it
meant
to
be
read?
33
4.3
Pascal
and its dialects:
Lingua franca
of
computer

Recursion
versus iteration: The
Tower
of
Hanoi 49
5.6 The
flag
of
Alfanumerica:
An
algorithmic
novel
on
iteration
and
recursion
52
6
SYNTAX
54
6.1
Syntax and
semantics
54
6.2
Grammars
and
their
representation:
Syntax

The role
of
syntax
analysis
63
7.2
Syntax analysis
of
parenthesis-free expressions
by
counting
64
7.3
Analysis
by
recursive
descent
66
7.4
Turning syntax
diagrams
into
a
parser
66
Part
III
Objects,
algorithms,
programs

"population
count"
73
9
ORDERED SETS
81
9.1
Sequential
search
82
9.2
Binary
search
83
9.3
In-place
permutation
86
10
STRINGS
93
10.1
Recognizing
a
pattern
consisting
of
a
single
string

102
11.4
Minimum spanning
tree
in
a
graph
104
Contents
vii
12
INTEGERS
107
12.1
Operations
on
integers
107
12.2
The
Euclidean
algorithm
110
12.3
The
prime
number
sieve
of
Eratosthenes

Homer's
method
123
13.4
Bisection
124
13.5
Newton's
method
for computing
the
square
root
125
14
STRAIGHT
LINES
AND
CIRCLES
129
14.1
Intersection
129
14.2
Clipping
132
14.3
Drawing
digitized
lines

ultimate RISC
148
15.2
Almost
nothing
is
computable
152
15.3
The
halting problem
is
undecidable
153
15.4
Computable,
yet
unknown
154
15.5
Multiplication
of
complex
numbers
156
vill
Contents
15.6
Complexity
of

divide-and-conquer
algorithms
169
16.6
Permutations
170
16.7
Trees
171
17
SORTING
AND
ITS COMPLEXITY
174
17.1
What
is
sorting?
How difficult
is
it?
174
17.2
Types
of
sorting
algorithms
177
17.3
Simple

Merging
and
merge sorts
188
17.8
Is it
possible
to
sort
in
linear
time?
191
17.9
Sorting networks
192
Part
V
Data
structures
197
18
WHAT
IS
A
DATA
STRUCTURE?
199
18.1
Data

19.2
Stack
206
19.3
First-in-first-out
queue
210
19.4
Priority
queue
212
19.5
Dictionary
213
20
IMPLICIT
DATA
STRUCTURES
218
20.1
What
is
an
implicit data
structure?
218
20.2
Array storage
219
20.3

management,
pointer
variables
234
21.2
The
fifo
queue
implemented
as
a one-way
list
237
21.3 Tree
traversal
238
21.4
Binary
search trees
248
21.5
Balanced
trees:
General
definition
252
21.6
Height-balanced
trees
254

a
priori
269
22.4
Conventional
hash
tables:
Collision
resolution
271
22.5
Choice
of
hash
function:
Randomization
276
22.6
Performance
analysis
278
22.7
Extendible
hashing
279
X
22.8
A
virtual
radix

structures:
Objectives and
constraints
288
23.5 The grid
file
290
23.6
Simple geometric objects
and
their
parameter
spaces
294
23.7
Region
queries
of
arbitrary
shape
296
23.8
Evaluating
region queries
with
a
grid
file
298
23.9

305
24.2
Convex
hull:
A
multitude
of
algorithms
307
24.3
The
uses
of
convexity: Basic operations
on
polygons
311
24.4 Visibility
in the plane: A
simple algorithm
whose
analysis
is
not
314
25
PLANE-SWEEP:
A
GENERAL-PURPOSE
ALGORITHM

324
25.4 Updating the
y-table
and detecting
an
intersection
325
25.5
Sweeping across
intersections
325
25.6 Degenerate
configurations,
numerical
errors,
robustness
326
26
THE
CLOSEST
PAIR
PROBLEM
329
26.1
The
problem
329
26.2 Plane-sweep applied
to the
closest pair

of
unconventional
coverage
and
style.
Let
us
explain
its
prerequisites and
aims,
so
that
the
reader
may
judge
whether
it
matches
his
or
her
background
and
goals.
This
is
not
a

point
of
view,
we
present
program fragments
in
an
open-ended,
extended dialect
of
Pascal
which
is
not
defined
formally.
We
rely
on
readers to
translate
these
constructs
into
a
programming
language
of
their

techniques
in
a
few
core areas
of
computer
science.
Even
though
we
regard
computer
science
as
the
technology
of
formalization,
we
rarely
present
our
topics
in
a
formal
manner.
In
an

intuition,
and
this
is
best achieved
by
packaging
the
idea
in
a
telling
example.
We
often
leave to the
reader
the
task
of
generalizing
the
jist
of
an
example
into
a
general
rule.

times
precludes
presenting
the
background
that
may
be
necessary
for
full
understanding.
This
is
the
case,
for
example,
in
our
brief
introduction
to
computability.
We
base
this
choice
on
the

an
early
first
exposure
facilitates
mastery
when
the
student
faces
these
funda-
mental
topics
in
more
depth
later
in
the
curriculum.
After
all
these
warnings
about
what
this
book
is

developed
powerful
ideas,
not
easily
reinvented,
that
can
be
turned
directly
into
tools
for
developing
good
programs.
Second,
we
wish
to
show
the
beginning
student
and
future
computer
scientist
a

lasting
value,
with
ideas
that
we
hope
will
outlive
the
current
generation
of
computers,
operating
systems,
and
programming
languages.
Our
expectation
of
the
half-life
of
a
topic
has
often
decided

for
Motion,
Graphics,
and
Geometry",
we
assume
that
the
reader
has
worked
with
one
or
two
computers,
operating
systems,
and
languages,
and
may
now
have
to
master
a
new
programming

largely
inde-
pendent
of
any
specific
environment.
We
begin
by
defining
a
toy
environment
designed
to
set
the
tone
and
highlight
simple
concepts
necessary
for
programming
motion,
geom-
etry,
and

the
fact
that
most
of
today's
programs
are
interactive
but
that
programming
techniques
for
interaction
are
not
widely
taught,
we
devote
a
section
to
dialog
control
and
show
examples
of

ease
the
programming
task
throughout
the
course.
In
order
to
get
started
right
away
on
interesting
and
attractive
demo
programs,
we
review
recursion-recursive
pictures
make
beautiful
examples
of
algorithm
animation.

inculcated
into
novices-namely,
that
every
semicolon
matters-but
it
comes
naturally
to
one
who
understands
thoroughly
how
syntax
is
processed.
To
breed
this
familiarity
with
syntactic
issues
that
allows
us
to

beginning
students
away
from
a
specific
system
they
have
learned,
and
to
drive
home
the
idea
that
most
programming
issues
are
"beyond
notation."
xiv
Preface
Part
III,
"Objects,
Algorithms, Programs",
builds

and
analysis.
We
use
the
following
selection
criteria:
1.
The
problems
must
be
real,
that
is, a
practical
programmer
is
likely
to
face
many
of
them
sooner
or
later;
they
can

possible,
we
have
tried
to
build
in an
element
of
surprise,
something to be
discovered,
something
more
than
meets
the
eye.
3.
These
algorithms
require only
the
simplest
of
data
structures-arrays.
More
elab-
orate

a
greater
depth
than
is
usual
in
an
introductory
text-such
as
the
phenomenon
of
the
braiding straight
lines.
Throughout
Part
III
we
introduce
by
example
the
basic
concepts
and
techniques
of

com-
putability
and
its
refinement, the
notion
of
complexity,
we
survey the
mathematical tools
commonly
used
in
algorithm
analysis.
We
illustrate
the use
of
these tools
by
presenting
classical
results
on
sorting,
an
important
topic

approach. Each
of
the
following
sections
presents
a
different type
of
data
structures:
implicit,
lists,
address computation.
We
use
this
variety to
illustrate
radically
different
implementations
of
(almost) the same
abstract
data
types:
to
make
the

data
structures
that
partition
space
according
to
predefined
grids.
Part
VI,
"Interaction Between Algorithms
and
Data
Structures: Case
Studies
in
Geometric Computation"
has
a
threefold
goal.
First,
we
want
to
show
convincingly
that
the

to
present
in
greater
depth one
coherent
area
where
a
particular
type
of
algorithm,
plane-sweep,
is
used
in
many
versions.
Third,
we
provide
an
introduction
to
a
novel
and
increasingly important discipline
in

subset suitable
to
his
Preface
xv
or
her
purpose,
here
is
the
dependency structure
of
the
various
parts
of
the
book.
Parts
I,
II,
and
III
form
the
"elementary
half'
of
the

feel
can
be
understood
on the
basis
of
high
school
mathematics,
whereas
the
second
half
makes
extensive
use
of
the
"mathematics
of
algorithm analysis", summarized
in
Chapter
16.
Parts
I,
II,
and
III

explicit
knowledge
of
precisely
those topics
treated
in
the
first half.
Thus
a
traditional course
on
data
structures
for
students who have taken
one or two introductory courses
in
computer
science
might
be
based
on
Chapters
16
to
26,
with Chapters

that
applies
to
almost
any
topic
treated
in
this book
is
to
program
and animate
the
execution
of
some
algorithm
on
a
sample
data
configuration.
To
acquaint the
student
early
with the necessary concepts
and
techniques, Part

ideas
of
that
chapter.
Parts
of
this
text
are
based
on
our book
Programmierung
und
Datenstrukturen
(Springer-Verlag,
1986),
but the
coverage has
been
greatly
expanded
and
revised.
We
have
developed
this
material over
the years

versity
of
Siegen, Germany;
and
the
University
of
Munster, Germany.
We
gratefully
acknowledge
the
helpful
contributions
of
former
and
present
students
and
colleagues
in
all
of
these
places: in
particular, David
Banks,
Kim
Blakeley, Christian Brechbuehler,

of
Texas
at
El
Paso,
Professor
Arunabhasen
of
Arizona
State
University,
and
Professor
Mario
Gerla
of
the
University
of
California
at
Los
Angeles. Finally,
we
thank
the
entire
team
at
Prentice

formal
notations.
Reducing
a
solution to
primitive
operations.
Programming as an
activity
independent
of
language.
The
Purpose
of
an
Artificial
Programming Environment
A
program
can
be
designed
with
the barest
of
tools,
paper
and
pencil,

environment,
typically
a
complex
system
with
many
distinct
components:
a
computer
and
its
operating
system,
utilities,
and
program
libraries;
text
and
program
editors;
various
program-
ming
languages
and
their
processors.

programming
environment.
Most
programmers
work
in
environments that
provide
very
powerful
operations
and
tools.
The
more
powerful
a
programming environment,
the
simpler the programming
task,
at
least
to
the expert
who
has
achieved
mastery
of

he
must
understand
before
he
can
write
the
simplest
program.
The
simpler
a
programming
environment,
the
easier
it is
to
write
and
run
small
programs,
and
the
more
work
it is
to write

with
an
assembler,
a loader,
and
a
small
program
library sufficed.
The
programs
they
wrote were small
compared
to
what
a
professional
programmer
writes
today.
The
simpler
a
programming
environment
is,
the
better suited
it

education
it
is
useful to
invent
artifi-
cial programming
environments.
Their
only purpose
is
to
illustrate some
important
concepts
in
the
simplest
possible setting
and
to
facilitate
insight.
Part
I
of
this
book
introduces
such

screen
is
a
powerful
new medium
for
communication. Visualization
often
makes
it
possible
to
present
the results
of
a
computation
in
intuitively
appealing
ways
that
convey
insights
not
easily
gained
in
any other
manner.

[NS
79],
[Rog
85], [Wat
89],
and
[Wol 89].
I
CHAPTER
1
Reducing
a
Task
to
Given
Primitives:
Programming
Motion
Primitives
for
specifying
motion.
Expressing
an
algorithm
in
informal
notations
and
in

programming environment
as
a
purely
mental exercise.
The
example
of
a
vehicle
that
moves
under program
control
in
a
fictitious
landscape
is
a
microcosmos
of
programming
lore.
In this
section
we
introduce
important
concepts that

halfway
between
the
grid
points
(Fig.
1.
1).
A
robot
car
enclosed within
the
wall
moves
along
this
grid
under computer
control,
one
step
at
a
time, from
grid
point
to
adjacent
grid point.

l l l l
S

7 r-l-r-~-n-~-7-i-r-
H I ^ 4 '-
Figure
1.1
The
robot's
cross-hairs
show
its
current location
on
the
grid.
The
robot
is
controlled
by
a
program that
uses
the
following
commands:
left
Turn
90

touching
a
wall
to
your
front,
send
program control
to
the
label
#.
A
program for
the
robot
is a
sequence
of
commands
with
distinct
labels. The
labels
serve
merely
to
identify
the
commands

control
is
redirected
by
either
of
the
goto
commands.
Example
The following program
moves
the
robot
forward
until
it
bumps
into
a
wall:
I
if
touch goto
4
2
forward
3
goto
1

wall-
finding
program
by
the simpler
statement
while
not touch
do
forward;
and then
translated
it
into the
robot's
language.
A
program
for this
robot
car
to
patrol
the
walls
of
a
city
consists
of

the
wall;
at
all
times,
keep
within
one step
of
it.
2.
Visit every spot
along
the
wall
in
a
monotonic progression.
The
mental
image
of
walking around
a
room
with
eyes closed,
left
arm
extended,

front.
As
the
robot
has no
sensor
on
its
left
side,
we
will
let it
turn
left
at
every
step to
sense
the wall
with
its
front bumper,
then
turn
right
to
resume
its
position

algorithm
described
in
English:
Clockwise, starting
at
left,
look
for
the first
direction not blocked
by
a
wall,
and
if
found,
take
a
step
in
that
direction.
Let
us
test this algorithm
on
some
critical
configurations. The

wall to
its
left-rear.
In
Fig.
1.4
the
robot
enters
a
blind
alley.
At
the
end
of
the
alley,
it
turns
clockwise
twice,
then
exits
by
the
route
it
entered.
Figure

to Given Primitives:
Programming
Motion
Chap.
1
1.3
ALGORITHM
SPECIFIED
IN
A
HIGH-LEVEL LANGUAGE
The ideas
presented informally
in
Section
1.2
are
made
precise
in the
following
elegant,
concise
program:
{
wall
to
left-rear
}
loop

to
left-rear)
forever;
[
wall
to
left-rear
}
Program
verification.
The
comments
in
braces
are
program
invariants:
asser-
tions
about
the
state
of
the
robot
that
are
true
every
time

position
and the
presence
of
a
nearby
wall
that
must
hold
for
each
assertion to
be
true
are
illustrated
in
Fig.
1.5.
Shaded
circles
indicate
points through
which
a
wall
must
pass.
Each

is a
predicate
transformer,
as
suggested
in
Fig.
1.6.

A- Figure
1.5
Three
types
of
invariants
wall
to
left-rear
wall
to
left-front
wall to
right-front
relate the

The
Robot's
Program
Optimized
loop
left;
while
touch
do
right;
endwhile;
forward;
forever;
2
3
4
5
6
7
left
if
touch
goto
4
goto
6
right
goto
2
forward

to
left-rear
Figure
1.6
Robot
motions
as
predicate transformers.
1.5
THE
ROBOT'S
PROGRAM
OPTIMIZED
In
designing
a
program
it
is
best to follow simple,
general
ideas,
and to
decide
on
details
in
the
most straightforward
manner,

memory requirements.
This process
of
program
transformation
can
often
be
done
syntactically, that
is,
merely
by
considering
the
definition
of
individual statements, not
the
algorithm
as
a
whole.
As
an
example,
we
derive
a
five-line

shown
on
the
right
side.
[
wall
to
left-rear
}
left
if
touch
goto
4
goto
6
[
wall
to
right-front
}
right
goto
2
forward
goto
I
£ wall
to

7
7
8
Reducing
a
Task to
Given Primitives: Programming
Motion
Chap.
1
An
optimization technique
called
loop
rotation
allows
us
to
shorten
this
program
by
yet
another
instruction.
It
changes
the
structure
of

can't
advance".
(
wall
to
right-front]
4
right
2
if
touch goto
4
6
forward
1
left
7
goto
2
PROGRAMMING
PROJECTS
1.
Design
a
data
structure suitable for storing
a
wall
made
up

and
animate
its
execution
when
tracking
a
wall
entered
with the wall-editor.
Specifically, show the
robot's
position
and
orientation after
each
change
of
state.
CHAPTER
2
Graphics
Primitives
and
Environments
Turtle
graphics.
QuickDraw:
A
graphics

in the
programming
language Logo,
turtle
graphics
primitives
are
now
available
for
several
computer
systems
and
languages.
They
come
in
different versions, but
the
essential
point
is
the
same
as
that
introduced
in the
example

depending
on
its
current
state:
move(s)
[
take
s
unit
steps
in the
direction
you
are
facing)
tum(d)
[
turn
counterclockwise
d
degrees
3
The
turtle's
initial
state
is
set
by

color
of
the
trail drawn
by
the
moving
pen:
pencolor(c)
{
where
c =
white,
black, none, etc.
}
9