%!PS-Adobe-3.0
%%BoundingBox: (atend)
%%Pages: (atend)
%%PageOrder: (atend)
%%DocumentFonts: (atend)
%%Creator: Frame 5.0
%%DocumentData: Clean7Bit
%%EndComments
%%BeginProlog
%
% Frame ps_prolog 5.0, for use with Frame 5.0 products
% This ps_prolog file is Copyright (c) 1986-1995 Frame Technology
% Corporation. All rights reserved. This ps_prolog file may be
% freely copied and distributed in conjunction with documents created
% using FrameMaker, FrameMaker/SGML and FrameViewer as long as this
% copyright notice is preserved.
%
% FrameMaker users specify the proper paper size for each print job in the
% "Print" dialog's "Printer Paper Size" "Width" and "Height~ fields. If the
% printer that the PS file is sent to does not support the requested paper
% size, or if there is no paper tray of the proper size currently installed,
% then the job will not be printed. The following flag, if set to true, will
% cause the job to print on the default paper in such cases.
/FMAllowPaperSizeMismatch false def
%
% Frame products normally print colors as their true color on a color printer
% or as shades of gray, based on luminance, on a black-and white printer. The
% following flag, if set to true, forces all non-white colors to print as pure
% black. This has no effect on bitmap images.
/FMPrintAllColorsAsBlack false def
%
% Frame products can either set their own line screens or use a printer's
% default settings. Three flags below control this separately for no
% separations, spot separations and process separations. If a flag
% is true, then the default printer settings will not be changed. If it is
% false, Frame products will use their own settings from a table based on
% the printer's resolution.
/FMUseDefaultNoSeparationScreen true def
/FMUseDefaultSpotSeparationScreen true def
/FMUseDefaultProcessSeparationScreen false def
%
% For any given PostScript printer resolution, Frame products have two sets of
% screen angles and frequencies for printing process separations, which are
% recomended by Adobe. The following variable chooses the higher frequencies
% when set to true or the lower frequencies when set to false. This is only
% effective if the appropriate FMUseDefault...SeparationScreen flag is false.
/FMUseHighFrequencyScreens true def
%
% The following is a set of predefined optimal frequencies and angles for various
% common dpi settings. This is taken from "Advances in Color Separation Using
% PostScript Software Technology," from Adobe Systems (3/13/89 P.N. LPS 0043)
% and corrolated with information which is in various PPD (4.0) files.
%
% The "dpiranges" figure is the minimum dots per inch device resolution which
% can support this setting. The "low" and "high" values are controlled by the
% setting of the FMUseHighFrequencyScreens flag above. The "TDot" flags control
% the use of the "Yellow Triple Dot" feature whereby the frequency id divided by
% three, but the dot function is "trippled" giving a block of 3x3 dots per cell.
%
% PatFreq is a compromise pattern frequency for ps Level 2 printers which is close
% to the ideal WYSIWYG pattern frequency of 9 repetitions/inch but does not beat
% (too badly) against the screen frequencies of any separations for that DPI.
/dpiranges [ 2540 2400 1693 1270 1200 635 600 0 ] def
/CMLowFreqs [ 100.402 94.8683 89.2289 100.402 94.8683 66.9349 63.2456 47.4342 ] def
/YLowFreqs [ 95.25 90.0 84.65 95.25 90.0 70.5556 66.6667 50.0 ] def
/KLowFreqs [ 89.8026 84.8528 79.8088 89.8026 84.8528 74.8355 70.7107 53.033 ] def
/CLowAngles [ 71.5651 71.5651 71.5651 71.5651 71.5651 71.5651 71.5651 71.5651 ] def
/MLowAngles [ 18.4349 18.4349 18.4349 18.4349 18.4349 18.4349 18.4349 18.4349 ] def
/YLowTDot [ true true false true true false false false ] def
/CMHighFreqs [ 133.87 126.491 133.843 108.503 102.523 100.402 94.8683 63.2456 ] def
/YHighFreqs [ 127.0 120.0 126.975 115.455 109.091 95.25 90.0 60.0 ] def
/KHighFreqs [ 119.737 113.137 119.713 128.289 121.218 89.8026 84.8528 63.6395 ] def
/CHighAngles [ 71.5651 71.5651 71.5651 70.0169 70.0169 71.5651 71.5651 71.5651 ] def
/MHighAngles [ 18.4349 18.4349 18.4349 19.9831 19.9831 18.4349 18.4349 18.4349 ] def
/YHighTDot [ false false true false false true true false ] def
/PatFreq [ 10.5833 10.0 9.4055 10.5833 10.0 10.5833 10.0 9.375 ] def
%
% PostScript Level 2 printers contain an "Accurate Screens" feature which can
% improve process separation rendering at the expense of compute time. This
% flag is ignored by PostScript Level 1 printers.
/FMUseAcccurateScreens true def
%
% The following PostScript procedure defines the spot function that Frame
% products will use for process separations. You may un-comment-out one of
% the alternative functions below, or use your own.
%
% Dot function
/FMSpotFunction {abs exch abs 2 copy add 1 gt
{1 sub dup mul exch 1 sub dup mul add 1 sub }
{dup mul exch dup mul add 1 exch sub }ifelse } def
%
% Line function
% /FMSpotFunction { pop } def
%
% Elipse function
% /FMSpotFunction { dup 5 mul 8 div mul exch dup mul exch add
% sqrt 1 exch sub } def
%
%
/FMversion (5.0) def
/fMLevel1 /languagelevel where {pop languagelevel} {1} ifelse 2 lt def
/FMPColor
fMLevel1 {
false
/colorimage where {pop pop true} if
} {
true
} ifelse
def
/FrameDict 400 dict def
systemdict /errordict known not {/errordict 10 dict def
errordict /rangecheck {stop} put} if
% The readline in PS 23.0 doesn't recognize cr's as nl's on AppleTalk
FrameDict /tmprangecheck errordict /rangecheck get put
errordict /rangecheck {FrameDict /bug true put} put
FrameDict /bug false put
mark
% Some PS machines read past the CR, so keep the following 3 lines together!
currentfile 5 string readline
00
0000000000
cleartomark
errordict /rangecheck FrameDict /tmprangecheck get put
FrameDict /bug get {
/readline {
/gstring exch def
/gfile exch def
/gindex 0 def
{
gfile read pop
dup 10 eq {exit} if
dup 13 eq {exit} if
gstring exch gindex exch put
/gindex gindex 1 add def
} loop
pop
gstring 0 gindex getinterval true
} bind def
} if
/FMshowpage /showpage load def
/FMquit /quit load def
/FMFAILURE {
dup = flush
FMshowpage
/Helvetica findfont 12 scalefont setfont
72 200 moveto show
72 220 moveto show
FMshowpage
FMquit
} def
/FMVERSION {
FMversion ne {
(Frame product version does not match ps_prolog! Check installation;)
(also check ~/fminit and ./fminit for old versions) FMFAILURE
} if
} def
/FMBADEPSF {
(Adobe's PostScript Language Reference Manual, 2nd Edition, section H.2.4)
(says your EPS file is not valid, as it calls X )
dup dup (X) search pop exch pop exch pop length
5 -1 roll
putinterval
FMFAILURE
} def
/fmConcatProcs
{
/proc2 exch cvlit def/proc1 exch cvlit def/newproc proc1 length proc2 length add array def
newproc 0 proc1 putinterval newproc proc1 length proc2 putinterval newproc cvx
}def
FrameDict begin [
/ALDsave
/FMdicttop
/FMoptop
/FMpointsize
/FMsaveobject
/b
/bitmapsave
/blut
/bpside
/bs
/bstring
/bwidth
/c
/cf
/cs
/cynu
/depth
/edown
/fh
/fillvals
/fw
/fx
/fy
/g
/gfile
/gindex
/grnt
/gryt
/gstring
/height
/hh
/i
/im
/indx
/is
/k
/kk
/landscape
/lb
/len
/llx
/lly
/m
/magu
/manualfeed
/n
/offbits
/onbits
/organgle
/orgbangle
/orgbfreq
/orgbproc
/orgbxfer
/orgfreq
/orggangle
/orggfreq
/orggproc
/orggxfer
/orgmatrix
/orgproc
/orgrangle
/orgrfreq
/orgrproc
/orgrxfer
/orgxfer
/pagesave
/paperheight
/papersizedict
/paperwidth
/pos
/pwid
/r
/rad
/redt
/sl
/str
/tran
/u
/urx
/ury
/val
/width
/width
/ws
/ww
/x
/x1
/x2
/xindex
/xpoint
/xscale
/xx
/y
/y1
/y2
/yelu
/yindex
/ypoint
/yscale
/yy
] { 0 def } forall
/FmBD {bind def} bind def
systemdict /pdfmark known {
/fMAcrobat true def
/FmPD /pdfmark load def
/FmPT /show load def
currentdistillerparams /CoreDistVersion get 2000 ge {
/FmPD2 /pdfmark load def
/FmPA { mark exch /Dest exch 5 3 roll
/View [ /XYZ null 6 -2 roll FmDC exch pop null] /DEST FmPD
}FmBD
} {
/FmPD2 /cleartomark load def
/FmPA {pop pop pop}FmBD
} ifelse
} {
/fMAcrobat false def
/FmPD /cleartomark load def
/FmPD2 /cleartomark load def
/FmPT /pop load def
/FmPA {pop pop pop}FmBD
} ifelse
/FmDC {
transform fMDefaultMatrix itransform cvi exch cvi exch
}FmBD
/FmBx {
dup 3 index lt {3 1 roll exch} if
1 index 4 index lt {4 -1 roll 3 1 roll exch 4 1 roll} if
}FmBD
/FMnone 0 def
/FMcyan 1 def
/FMmagenta 2 def
/FMyellow 3 def
/FMblack 4 def
/FMcustom 5 def
/fMNegative false def
/FrameSepIs FMnone def
/FrameSepBlack 0 def
/FrameSepYellow 0 def
/FrameSepMagenta 0 def
/FrameSepCyan 0 def
/FrameSepRed 1 def
/FrameSepGreen 1 def
/FrameSepBlue 1 def
/FrameCurGray 1 def
/FrameCurPat null def
/FrameCurColors [ 0 0 0 1 0 0 0 ] def
/FrameColorEpsilon .001 def
/eqepsilon {
sub dup 0 lt {neg} if
FrameColorEpsilon le
} bind def
/FrameCmpColorsCMYK {
2 copy 0 get exch 0 get eqepsilon {
2 copy 1 get exch 1 get eqepsilon {
2 copy 2 get exch 2 get eqepsilon {
3 get exch 3 get eqepsilon
} {pop pop false} ifelse
}{pop pop false} ifelse
} {pop pop false} ifelse
} bind def
/FrameCmpColorsRGB {
2 copy 4 get exch 0 get eqepsilon {
2 copy 5 get exch 1 get eqepsilon {
6 get exch 2 get eqepsilon
}{pop pop false} ifelse
} {pop pop false} ifelse
} bind def
/RGBtoCMYK {
1 exch sub
3 1 roll
1 exch sub
3 1 roll
1 exch sub
3 1 roll
3 copy
2 copy
le { pop } { exch pop } ifelse
2 copy
le { pop } { exch pop } ifelse
dup dup dup
6 1 roll
4 1 roll
7 1 roll
sub
6 1 roll
sub
5 1 roll
sub
4 1 roll
} bind def
/CMYKtoRGB {
dup dup 4 -1 roll add
5 1 roll 3 -1 roll add
4 1 roll add
1 exch sub dup 0 lt {pop 0} if 3 1 roll
1 exch sub dup 0 lt {pop 0} if exch
1 exch sub dup 0 lt {pop 0} if exch
} bind def
/FrameSepInit {
1.0 RealSetgray
} bind def
/FrameSetSepColor {
/FrameSepBlue exch def
/FrameSepGreen exch def
/FrameSepRed exch def
/FrameSepBlack exch def
/FrameSepYellow exch def
/FrameSepMagenta exch def
/FrameSepCyan exch def
/FrameSepIs FMcustom def
setCurrentScreen
} bind def
/FrameSetCyan {
/FrameSepBlue 1.0 def
/FrameSepGreen 1.0 def
/FrameSepRed 0.0 def
/FrameSepBlack 0.0 def
/FrameSepYellow 0.0 def
/FrameSepMagenta 0.0 def
/FrameSepCyan 1.0 def
/FrameSepIs FMcyan def
setCurrentScreen
} bind def
/FrameSetMagenta {
/FrameSepBlue 1.0 def
/FrameSepGreen 0.0 def
/FrameSepRed 1.0 def
/FrameSepBlack 0.0 def
/FrameSepYellow 0.0 def
/FrameSepMagenta 1.0 def
/FrameSepCyan 0.0 def
/FrameSepIs FMmagenta def
setCurrentScreen
} bind def
/FrameSetYellow {
/FrameSepBlue 0.0 def
/FrameSepGreen 1.0 def
/FrameSepRed 1.0 def
/FrameSepBlack 0.0 def
/FrameSepYellow 1.0 def
/FrameSepMagenta 0.0 def
/FrameSepCyan 0.0 def
/FrameSepIs FMyellow def
setCurrentScreen
} bind def
/FrameSetBlack {
/FrameSepBlue 0.0 def
/FrameSepGreen 0.0 def
/FrameSepRed 0.0 def
/FrameSepBlack 1.0 def
/FrameSepYellow 0.0 def
/FrameSepMagenta 0.0 def
/FrameSepCyan 0.0 def
/FrameSepIs FMblack def
setCurrentScreen
} bind def
/FrameNoSep {
/FrameSepIs FMnone def
setCurrentScreen
} bind def
/FrameSetSepColors {
FrameDict begin
[ exch 1 add 1 roll ]
/FrameSepColors
exch def end
} bind def
/FrameColorInSepListCMYK {
FrameSepColors {
exch dup 3 -1 roll
FrameCmpColorsCMYK
{ pop true exit } if
} forall
dup true ne {pop false} if
} bind def
/FrameColorInSepListRGB {
FrameSepColors {
exch dup 3 -1 roll
FrameCmpColorsRGB
{ pop true exit } if
} forall
dup true ne {pop false} if
} bind def
/RealSetgray /setgray load def
/RealSetrgbcolor /setrgbcolor load def
/RealSethsbcolor /sethsbcolor load def
end
/setgray {
FrameDict begin
FrameSepIs FMnone eq
{ RealSetgray }
{
FrameSepIs FMblack eq
{ RealSetgray }
{ FrameSepIs FMcustom eq
FrameSepRed 0 eq and
FrameSepGreen 0 eq and
FrameSepBlue 0 eq and {
RealSetgray
} {
1 RealSetgray pop
} ifelse
} ifelse
} ifelse
end
} bind def
/setrgbcolor {
FrameDict begin
FrameSepIs FMnone eq
{ RealSetrgbcolor }
{
3 copy [ 4 1 roll ]
FrameColorInSepListRGB
{
FrameSepBlue eq exch
FrameSepGreen eq and exch
FrameSepRed eq and
{ 0 } { 1 } ifelse
}
{
FMPColor {
RealSetrgbcolor
currentcmykcolor
} {
RGBtoCMYK
} ifelse
FrameSepIs FMblack eq
{1.0 exch sub 4 1 roll pop pop pop} {
FrameSepIs FMyellow eq
{pop 1.0 exch sub 3 1 roll pop pop} {
FrameSepIs FMmagenta eq
{pop pop 1.0 exch sub exch pop } {
FrameSepIs FMcyan eq
{pop pop pop 1.0 exch sub }
{pop pop pop pop 1} ifelse } ifelse } ifelse } ifelse
} ifelse
RealSetgray
}
ifelse
end
} bind def
/sethsbcolor {
FrameDict begin
FrameSepIs FMnone eq
{ RealSethsbcolor }
{
RealSethsbcolor
currentrgbcolor
setrgbcolor
}
ifelse
end
} bind def
FrameDict begin
/setcmykcolor where {
pop /RealSetcmykcolor /setcmykcolor load def
} {
/RealSetcmykcolor {
4 1 roll
3 { 3 index add 0 max 1 min 1 exch sub 3 1 roll} repeat
RealSetrgbcolor pop
} bind def
} ifelse
userdict /setcmykcolor {
FrameDict begin
FrameSepIs FMnone eq
{ RealSetcmykcolor }
{
4 copy [ 5 1 roll ]
FrameColorInSepListCMYK
{
FrameSepBlack eq exch
FrameSepYellow eq and exch
FrameSepMagenta eq and exch
FrameSepCyan eq and
{ 0 } { 1 } ifelse
}
{
FrameSepIs FMblack eq
{1.0 exch sub 4 1 roll pop pop pop} {
FrameSepIs FMyellow eq
{pop 1.0 exch sub 3 1 roll pop pop} {
FrameSepIs FMmagenta eq
{pop pop 1.0 exch sub exch pop } {
FrameSepIs FMcyan eq
{pop pop pop 1.0 exch sub }
{pop pop pop pop 1} ifelse } ifelse } ifelse } ifelse
} ifelse
RealSetgray
}
ifelse
end
} bind put
fMLevel1 {
/patScreenDict 7 dict dup begin
<0f1e3c78f0e1c387> [ 45 { pop } {exch pop} .5 2 sqrt] FmBD
<0f87c3e1f0783c1e> [ 135 { pop } {exch pop} .5 2 sqrt] FmBD
[ 0 { pop } dup .5 2 ] FmBD
[ 90 { pop } dup .5 2 ] FmBD
<8142241818244281> [ 45 { 2 copy lt {exch} if pop} dup .75 2 sqrt] FmBD
<03060c183060c081> [ 45 { pop } {exch pop} .875 2 sqrt] FmBD
<8040201008040201> [ 135 { pop } {exch pop} .875 2 sqrt] FmBD
end def
} {
/patProcDict 5 dict dup begin
<0f1e3c78f0e1c387> { 3 setlinewidth -1 -1 moveto 9 9 lineto stroke
4 -4 moveto 12 4 lineto stroke
-4 4 moveto 4 12 lineto stroke} bind def
<0f87c3e1f0783c1e> { 3 setlinewidth -1 9 moveto 9 -1 lineto stroke
-4 4 moveto 4 -4 lineto stroke
4 12 moveto 12 4 lineto stroke} bind def
<8142241818244281> { 1 setlinewidth -1 9 moveto 9 -1 lineto stroke
-1 -1 moveto 9 9 lineto stroke } bind def
<03060c183060c081> { 1 setlinewidth -1 -1 moveto 9 9 lineto stroke
4 -4 moveto 12 4 lineto stroke
-4 4 moveto 4 12 lineto stroke} bind def
<8040201008040201> { 1 setlinewidth -1 9 moveto 9 -1 lineto stroke
-4 4 moveto 4 -4 lineto stroke
4 12 moveto 12 4 lineto stroke} bind def
end def
/patDict 15 dict dup begin
/PatternType 1 def
/PaintType 2 def
/TilingType 3 def
/BBox [ 0 0 8 8 ] def
/XStep 8 def
/YStep 8 def
/PaintProc {
begin
patProcDict bstring known {
patProcDict bstring get exec
} {
8 8 true [1 0 0 -1 0 8] bstring imagemask
} ifelse
end
} bind def
end def
} ifelse
/combineColor {
FrameSepIs FMnone eq
{
graymode fMLevel1 or not {
[/Pattern [/DeviceCMYK]] setcolorspace
FrameCurColors 0 4 getinterval aload pop FrameCurPat setcolor
} {
FrameCurColors 3 get 1.0 ge {
FrameCurGray RealSetgray
} {
fMAcrobat not FMPColor graymode and and {
0 1 3 {
FrameCurColors exch get
1 FrameCurGray sub mul
} for
RealSetcmykcolor
} {
4 1 6 {
FrameCurColors exch get
graymode {
1 exch sub 1 FrameCurGray sub mul 1 exch sub
} {
1.0 lt {FrameCurGray} {1} ifelse
} ifelse
} for
RealSetrgbcolor
} ifelse
} ifelse
} ifelse
} {
FrameCurColors 0 4 getinterval aload
FrameColorInSepListCMYK {
FrameSepBlack eq exch
FrameSepYellow eq and exch
FrameSepMagenta eq and exch
FrameSepCyan eq and
FrameSepIs FMcustom eq and
{ FrameCurGray } { 1 } ifelse
} {
FrameSepIs FMblack eq
{FrameCurGray 1.0 exch sub mul 1.0 exch sub 4 1 roll pop pop pop} {
FrameSepIs FMyellow eq
{pop FrameCurGray 1.0 exch sub mul 1.0 exch sub 3 1 roll pop pop} {
FrameSepIs FMmagenta eq
{pop pop FrameCurGray 1.0 exch sub mul 1.0 exch sub exch pop } {
FrameSepIs FMcyan eq
{pop pop pop FrameCurGray 1.0 exch sub mul 1.0 exch sub }
{pop pop pop pop 1} ifelse } ifelse } ifelse } ifelse
} ifelse
graymode fMLevel1 or not {
[/Pattern [/DeviceGray]] setcolorspace
FrameCurPat setcolor
} {
graymode not fMLevel1 and {
dup 1 lt {pop FrameCurGray} if
} if
RealSetgray
} ifelse
} ifelse
} bind def
/savematrix {
orgmatrix currentmatrix pop
} bind def
/restorematrix {
orgmatrix setmatrix
} bind def
/fMDefaultMatrix matrix defaultmatrix def
/fMatrix2 matrix def
/dpi 72 0 fMDefaultMatrix dtransform
dup mul exch dup mul add sqrt def
/freq dpi dup 72 div round dup 0 eq {pop 1} if 8 mul div def
/sangle 1 0 fMDefaultMatrix dtransform exch atan def
sangle fMatrix2 rotate
fMDefaultMatrix fMatrix2 concatmatrix
dup 0 get /sflipx exch def
3 get /sflipy exch def
/screenIndex {
0 1 dpiranges length 1 sub { dup dpiranges exch get 1 sub dpi le {exit} {pop} ifelse } for
} bind def
/getCyanScreen {
FMUseHighFrequencyScreens { CHighAngles CMHighFreqs} {CLowAngles CMLowFreqs} ifelse
screenIndex dup 3 1 roll get 3 1 roll get /FMSpotFunction load
} bind def
/getMagentaScreen {
FMUseHighFrequencyScreens { MHighAngles CMHighFreqs } {MLowAngles CMLowFreqs} ifelse
screenIndex dup 3 1 roll get 3 1 roll get /FMSpotFunction load
} bind def
/getYellowScreen {
FMUseHighFrequencyScreens { YHighTDot YHighFreqs} { YLowTDot YLowFreqs } ifelse
screenIndex dup 3 1 roll get 3 1 roll get { 3 div
{2 { 1 add 2 div 3 mul dup floor sub 2 mul 1 sub exch} repeat
FMSpotFunction } } {/FMSpotFunction load } ifelse
0.0 exch
} bind def
/getBlackScreen {
FMUseHighFrequencyScreens { KHighFreqs } { KLowFreqs } ifelse
screenIndex get 45.0 /FMSpotFunction load
} bind def
/getSpotScreen {
getBlackScreen
} bind def
/getCompositeScreen {
getBlackScreen
} bind def
/FMSetScreen
fMLevel1 { /setscreen load
}{ {
8 dict begin
/HalftoneType 1 def
/SpotFunction exch def
/Angle exch def
/Frequency exch def
/AccurateScreens FMUseAcccurateScreens def
currentdict end sethalftone
} bind } ifelse
def
/setDefaultScreen {
FMPColor {
orgrxfer cvx orggxfer cvx orgbxfer cvx orgxfer cvx setcolortransfer
}
{
orgxfer cvx settransfer
} ifelse
orgfreq organgle orgproc cvx setscreen
} bind def
/setCurrentScreen {
FrameSepIs FMnone eq {
FMUseDefaultNoSeparationScreen {
setDefaultScreen
} {
getCompositeScreen FMSetScreen
} ifelse
} {
FrameSepIs FMcustom eq {
FMUseDefaultSpotSeparationScreen {
setDefaultScreen
} {
getSpotScreen FMSetScreen
} ifelse
} {
FMUseDefaultProcessSeparationScreen {
setDefaultScreen
} {
FrameSepIs FMcyan eq {
getCyanScreen FMSetScreen
} {
FrameSepIs FMmagenta eq {
getMagentaScreen FMSetScreen
} {
FrameSepIs FMyellow eq {
getYellowScreen FMSetScreen
} {
getBlackScreen FMSetScreen
} ifelse
} ifelse
} ifelse
} ifelse
} ifelse
} ifelse
} bind def
end
/FMDOCUMENT {
array /FMfonts exch def
/#copies exch def
FrameDict begin
0 ne /manualfeed exch def
/paperheight exch def
/paperwidth exch def
0 ne /fMNegative exch def
0 ne /edown exch def
/yscale exch def
/xscale exch def
fMLevel1 {
manualfeed {setmanualfeed} if
/FMdicttop countdictstack 1 add def
/FMoptop count def
setpapername
manualfeed {true} {papersize} ifelse
{manualpapersize} {false} ifelse
{desperatepapersize} {false} ifelse
{papersizefailure} if
count -1 FMoptop {pop pop} for
countdictstack -1 FMdicttop {pop end} for
}
{2 dict
dup /PageSize [paperwidth paperheight] put
manualfeed {dup /ManualFeed manualfeed put} if
{setpagedevice} stopped {papersizefailure} if
}
ifelse
FMPColor {
currentcolorscreen
cvlit /orgproc exch def
/organgle exch def
/orgfreq exch def
cvlit /orgbproc exch def
/orgbangle exch def
/orgbfreq exch def
cvlit /orggproc exch def
/orggangle exch def
/orggfreq exch def
cvlit /orgrproc exch def
/orgrangle exch def
/orgrfreq exch def
currentcolortransfer
fMNegative {
1 1 4 {
pop { 1 exch sub } fmConcatProcs 4 1 roll
} for
4 copy
setcolortransfer
} if
cvlit /orgxfer exch def
cvlit /orgbxfer exch def
cvlit /orggxfer exch def
cvlit /orgrxfer exch def
} {
currentscreen
cvlit /orgproc exch def
/organgle exch def
/orgfreq exch def
currenttransfer
fMNegative {
{ 1 exch sub } fmConcatProcs
dup settransfer
} if
cvlit /orgxfer exch def
} ifelse
end
} def
/FMBEGINPAGE {
FrameDict begin
/pagesave save def
3.86 setmiterlimit
/landscape exch 0 ne def
landscape {
90 rotate 0 exch dup /pwid exch def neg translate pop
}{
pop /pwid exch def
} ifelse
edown { [-1 0 0 1 pwid 0] concat } if
0 0 moveto paperwidth 0 lineto paperwidth paperheight lineto
0 paperheight lineto 0 0 lineto 1 setgray fill
xscale yscale scale
/orgmatrix matrix def
gsave
} def
/FMENDPAGE {
grestore
pagesave restore
end
showpage
} def
/FMFONTDEFINE {
FrameDict begin
findfont
ReEncode
1 index exch
definefont
FMfonts 3 1 roll
put
end
} def
/FMFILLS {
FrameDict begin dup
array /fillvals exch def
dict /patCache exch def
end
} def
/FMFILL {
FrameDict begin
fillvals 3 1 roll put
end
} def
/FMNORMALIZEGRAPHICS {
newpath
1 setlinewidth
0 setlinecap
0 0 0 sethsbcolor
0 setgray
} bind def
/FMBEGINEPSF {
end
/FMEPSF save def
/showpage {} def
% See Adobe's "PostScript Language Reference Manual, 2nd Edition", page 714.
% "...the following operators MUST NOT be used in an EPS file:" (emphasis ours)
/banddevice {(banddevice) FMBADEPSF} def
/clear {(clear) FMBADEPSF} def
/cleardictstack {(cleardictstack) FMBADEPSF} def
/copypage {(copypage) FMBADEPSF} def
/erasepage {(erasepage) FMBADEPSF} def
/exitserver {(exitserver) FMBADEPSF} def
/framedevice {(framedevice) FMBADEPSF} def
/grestoreall {(grestoreall) FMBADEPSF} def
/initclip {(initclip) FMBADEPSF} def
/initgraphics {(initgraphics) FMBADEPSF} def
/quit {(quit) FMBADEPSF} def
/renderbands {(renderbands) FMBADEPSF} def
/setglobal {(setglobal) FMBADEPSF} def
/setpagedevice {(setpagedevice) FMBADEPSF} def
/setshared {(setshared) FMBADEPSF} def
/startjob {(startjob) FMBADEPSF} def
/lettertray {(lettertray) FMBADEPSF} def
/letter {(letter) FMBADEPSF} def
/lettersmall {(lettersmall) FMBADEPSF} def
/11x17tray {(11x17tray) FMBADEPSF} def
/11x17 {(11x17) FMBADEPSF} def
/ledgertray {(ledgertray) FMBADEPSF} def
/ledger {(ledger) FMBADEPSF} def
/legaltray {(legaltray) FMBADEPSF} def
/legal {(legal) FMBADEPSF} def
/statementtray {(statementtray) FMBADEPSF} def
/statement {(statement) FMBADEPSF} def
/executivetray {(executivetray) FMBADEPSF} def
/executive {(executive) FMBADEPSF} def
/a3tray {(a3tray) FMBADEPSF} def
/a3 {(a3) FMBADEPSF} def
/a4tray {(a4tray) FMBADEPSF} def
/a4 {(a4) FMBADEPSF} def
/a4small {(a4small) FMBADEPSF} def
/b4tray {(b4tray) FMBADEPSF} def
/b4 {(b4) FMBADEPSF} def
/b5tray {(b5tray) FMBADEPSF} def
/b5 {(b5) FMBADEPSF} def
FMNORMALIZEGRAPHICS
[/fy /fx /fh /fw /ury /urx /lly /llx] {exch def} forall
fx fw 2 div add fy fh 2 div add translate
rotate
fw 2 div neg fh 2 div neg translate
fw urx llx sub div fh ury lly sub div scale
llx neg lly neg translate
/FMdicttop countdictstack 1 add def
/FMoptop count def
} bind def
/FMENDEPSF {
count -1 FMoptop {pop pop} for
countdictstack -1 FMdicttop {pop end} for
FMEPSF restore
FrameDict begin
} bind def
FrameDict begin
/setmanualfeed {
%%BeginFeature *ManualFeed True
statusdict /manualfeed true put
%%EndFeature
} bind def
/max {2 copy lt {exch} if pop} bind def
/min {2 copy gt {exch} if pop} bind def
/inch {72 mul} def
/pagedimen {
paperheight sub abs 16 lt exch
paperwidth sub abs 16 lt and
{/papername exch def} {pop} ifelse
} bind def
/setpapername {
/papersizedict 14 dict def
papersizedict begin
/papername /unknown def
/Letter 8.5 inch 11.0 inch pagedimen
/LetterSmall 7.68 inch 10.16 inch pagedimen
/Tabloid 11.0 inch 17.0 inch pagedimen
/Ledger 17.0 inch 11.0 inch pagedimen
/Legal 8.5 inch 14.0 inch pagedimen
/Statement 5.5 inch 8.5 inch pagedimen
/Executive 7.5 inch 10.0 inch pagedimen
/A3 11.69 inch 16.5 inch pagedimen
/A4 8.26 inch 11.69 inch pagedimen
/A4Small 7.47 inch 10.85 inch pagedimen
/B4 10.125 inch 14.33 inch pagedimen
/B5 7.16 inch 10.125 inch pagedimen
end
} bind def
/papersize {
papersizedict begin
/Letter {lettertray letter} def
/LetterSmall {lettertray lettersmall} def
/Tabloid {11x17tray 11x17} def
/Ledger {ledgertray ledger} def
/Legal {legaltray legal} def
/Statement {statementtray statement} def
/Executive {executivetray executive} def
/A3 {a3tray a3} def
/A4 {a4tray a4} def
/A4Small {a4tray a4small} def
/B4 {b4tray b4} def
/B5 {b5tray b5} def
/unknown {unknown} def
papersizedict dup papername known {papername} {/unknown} ifelse get
end
statusdict begin stopped end
} bind def
/manualpapersize {
papersizedict begin
/Letter {letter} def
/LetterSmall {lettersmall} def
/Tabloid {11x17} def
/Ledger {ledger} def
/Legal {legal} def
/Statement {statement} def
/Executive {executive} def
/A3 {a3} def
/A4 {a4} def
/A4Small {a4small} def
/B4 {b4} def
/B5 {b5} def
/unknown {unknown} def
papersizedict dup papername known {papername} {/unknown} ifelse get
end
stopped
} bind def
/desperatepapersize {
statusdict /setpageparams known
{
paperwidth paperheight 0 1
statusdict begin
{setpageparams} stopped
end
} {true} ifelse
} bind def
/papersizefailure {
FMAllowPaperSizeMismatch not
{
(The requested paper size is not available in any currently-installed tray)
(Edit the PS file to "FMAllowPaperSizeMismatch true" to use default tray)
FMFAILURE } if
} def
/DiacriticEncoding [
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /space /exclam /quotedbl
/numbersign /dollar /percent /ampersand /quotesingle /parenleft
/parenright /asterisk /plus /comma /hyphen /period /slash /zero /one
/two /three /four /five /six /seven /eight /nine /colon /semicolon
/less /equal /greater /question /at /A /B /C /D /E /F /G /H /I /J /K
/L /M /N /O /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash
/bracketright /asciicircum /underscore /grave /a /b /c /d /e /f /g /h
/i /j /k /l /m /n /o /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar
/braceright /asciitilde /.notdef /Adieresis /Aring /Ccedilla /Eacute
/Ntilde /Odieresis /Udieresis /aacute /agrave /acircumflex /adieresis
/atilde /aring /ccedilla /eacute /egrave /ecircumflex /edieresis
/iacute /igrave /icircumflex /idieresis /ntilde /oacute /ograve
/ocircumflex /odieresis /otilde /uacute /ugrave /ucircumflex
/udieresis /dagger /.notdef /cent /sterling /section /bullet
/paragraph /germandbls /registered /copyright /trademark /acute
/dieresis /.notdef /AE /Oslash /.notdef /.notdef /.notdef /.notdef
/yen /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/ordfeminine /ordmasculine /.notdef /ae /oslash /questiondown
/exclamdown /logicalnot /.notdef /florin /.notdef /.notdef
/guillemotleft /guillemotright /ellipsis /.notdef /Agrave /Atilde
/Otilde /OE /oe /endash /emdash /quotedblleft /quotedblright
/quoteleft /quoteright /.notdef /.notdef /ydieresis /Ydieresis
/fraction /currency /guilsinglleft /guilsinglright /fi /fl /daggerdbl
/periodcentered /quotesinglbase /quotedblbase /perthousand
/Acircumflex /Ecircumflex /Aacute /Edieresis /Egrave /Iacute
/Icircumflex /Idieresis /Igrave /Oacute /Ocircumflex /.notdef /Ograve
/Uacute /Ucircumflex /Ugrave /dotlessi /circumflex /tilde /macron
/breve /dotaccent /ring /cedilla /hungarumlaut /ogonek /caron
] def
/ReEncode {
dup
length
dict begin
{
1 index /FID ne
{def}
{pop pop} ifelse
} forall
0 eq {/Encoding DiacriticEncoding def} if
currentdict
end
} bind def
FMPColor
{
/BEGINBITMAPCOLOR {
BITMAPCOLOR} def
/BEGINBITMAPCOLORc {
BITMAPCOLORc} def
/BEGINBITMAPTRUECOLOR {
BITMAPTRUECOLOR } def
/BEGINBITMAPTRUECOLORc {
BITMAPTRUECOLORc } def
/BEGINBITMAPCMYK {
BITMAPCMYK } def
/BEGINBITMAPCMYKc {
BITMAPCMYKc } def
}
{
/BEGINBITMAPCOLOR {
BITMAPGRAY} def
/BEGINBITMAPCOLORc {
BITMAPGRAYc} def
/BEGINBITMAPTRUECOLOR {
BITMAPTRUEGRAY } def
/BEGINBITMAPTRUECOLORc {
BITMAPTRUEGRAYc } def
/BEGINBITMAPCMYK {
BITMAPCMYKGRAY } def
/BEGINBITMAPCMYKc {
BITMAPCMYKGRAYc } def
}
ifelse
/K {
FMPrintAllColorsAsBlack {
dup 1 eq 2 index 1 eq and 3 index 1 eq and not
{7 {pop} repeat 0 0 0 1 0 0 0} if
} if
FrameCurColors astore
pop combineColor
} bind def
/graymode true def
fMLevel1 {
/fmGetFlip {
fMatrix2 exch get mul 0 lt { -1 } { 1 } ifelse
} FmBD
} if
/setPatternMode {
fMLevel1 {
2 index patScreenDict exch known {
pop pop
patScreenDict exch get aload pop
freq
mul
5 2 roll
fMatrix2 currentmatrix 1 get 0 ne {
3 -1 roll 90 add 3 1 roll
sflipx 1 fmGetFlip sflipy 2 fmGetFlip neg mul
} {
sflipx 0 fmGetFlip sflipy 3 fmGetFlip mul
} ifelse
0 lt {exch pop} {pop} ifelse
fMNegative {
{neg} fmConcatProcs
} if
bind
systemdict /setscreen get exec
/FrameCurGray exch def
} {
/bwidth exch def
/bpside exch def
/bstring exch def
/onbits 0 def /offbits 0 def
freq sangle landscape {90 add} if
{/ypoint exch def
/xpoint exch def
/xindex xpoint 1 add 2 div bpside mul cvi def
/yindex ypoint 1 add 2 div bpside mul cvi def
bstring yindex bwidth mul xindex 8 idiv add get
1 7 xindex 8 mod sub bitshift and 0 ne fMNegative {not} if
{/onbits onbits 1 add def 1}
{/offbits offbits 1 add def 0}
ifelse
}
setscreen
offbits offbits onbits add div fMNegative {1.0 exch sub} if
/FrameCurGray exch def
} ifelse
} {
pop pop
dup patCache exch known {
patCache exch get
} {
dup
patDict /bstring 3 -1 roll put
patDict
9 PatFreq screenIndex get div dup matrix scale
makepattern
dup
patCache 4 -1 roll 3 -1 roll put
} ifelse
/FrameCurGray 0 def
/FrameCurPat exch def
} ifelse
/graymode false def
combineColor
} bind def
/setGrayScaleMode {
graymode not {
/graymode true def
fMLevel1 {
setCurrentScreen
} if
} if
/FrameCurGray exch def
combineColor
} bind def
/normalize {
transform round exch round exch itransform
} bind def
/dnormalize {
dtransform round exch round exch idtransform
} bind def
/lnormalize {
0 dtransform exch cvi 2 idiv 2 mul 1 add exch idtransform pop
} bind def
/H {
lnormalize setlinewidth
} bind def
/Z {
setlinecap
} bind def
/PFill {
graymode fMLevel1 or not {
gsave 1 setgray eofill grestore
} if
} bind def
/PStroke {
graymode fMLevel1 or not {
gsave 1 setgray stroke grestore
} if
stroke
} bind def
/X {
fillvals exch get
dup type /stringtype eq
{8 1 setPatternMode}
{setGrayScaleMode}
ifelse
} bind def
/V {
PFill gsave eofill grestore
} bind def
/Vclip {
clip
} bind def
/Vstrk {
currentlinewidth exch setlinewidth PStroke setlinewidth
} bind def
/N {
PStroke
} bind def
/Nclip {
strokepath clip newpath
} bind def
/Nstrk {
currentlinewidth exch setlinewidth PStroke setlinewidth
} bind def
/M {newpath moveto} bind def
/E {lineto} bind def
/D {curveto} bind def
/O {closepath} bind def
/L {
/n exch def
newpath
normalize
moveto
2 1 n {pop normalize lineto} for
} bind def
/Y {
L
closepath
} bind def
/R {
/y2 exch def
/x2 exch def
/y1 exch def
/x1 exch def
x1 y1
x2 y1
x2 y2
x1 y2
4 Y
} bind def
/rarc
{rad
arcto
} bind def
/RR {
/rad exch def
normalize
/y2 exch def
/x2 exch def
normalize
/y1 exch def
/x1 exch def
mark
newpath
{
x1 y1 rad add moveto
x1 y2 x2 y2 rarc
x2 y2 x2 y1 rarc
x2 y1 x1 y1 rarc
x1 y1 x1 y2 rarc
closepath
} stopped {x1 y1 x2 y2 R} if
cleartomark
} bind def
/RRR {
/rad exch def
normalize /y4 exch def /x4 exch def
normalize /y3 exch def /x3 exch def
normalize /y2 exch def /x2 exch def
normalize /y1 exch def /x1 exch def
newpath
normalize moveto
mark
{
x2 y2 x3 y3 rarc
x3 y3 x4 y4 rarc
x4 y4 x1 y1 rarc
x1 y1 x2 y2 rarc
closepath
} stopped
{x1 y1 x2 y2 x3 y3 x4 y4 newpath moveto lineto lineto lineto closepath} if
cleartomark
} bind def
/C {
grestore
gsave
R
clip
setCurrentScreen
} bind def
/CP {
grestore
gsave
Y
clip
setCurrentScreen
} bind def
/F {
FMfonts exch get
FMpointsize scalefont
setfont
} bind def
/Q {
/FMpointsize exch def
F
} bind def
/T {
moveto show
} bind def
/RF {
rotate
0 ne {-1 1 scale} if
} bind def
/TF {
gsave
moveto
RF
show
grestore
} bind def
/P {
moveto
0 32 3 2 roll widthshow
} bind def
/PF {
gsave
moveto
RF
0 32 3 2 roll widthshow
grestore
} bind def
/S {
moveto
0 exch ashow
} bind def
/SF {
gsave
moveto
RF
0 exch ashow
grestore
} bind def
/B {
moveto
0 32 4 2 roll 0 exch awidthshow
} bind def
/BF {
gsave
moveto
RF
0 32 4 2 roll 0 exch awidthshow
grestore
} bind def
/G {
gsave
newpath
normalize translate 0.0 0.0 moveto
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
PFill fill
grestore
} bind def
/Gstrk {
savematrix
newpath
2 index 2 div add exch 3 index 2 div sub exch
normalize 2 index 2 div sub exch 3 index 2 div add exch
translate
scale
0.0 0.0 1.0 5 3 roll arc
restorematrix
currentlinewidth exch setlinewidth PStroke setlinewidth
} bind def
/Gclip {
newpath
savematrix
normalize translate 0.0 0.0 moveto
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
clip newpath
restorematrix
} bind def
/GG {
gsave
newpath
normalize translate 0.0 0.0 moveto
rotate
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
PFill
fill
grestore
} bind def
/GGclip {
savematrix
newpath
normalize translate 0.0 0.0 moveto
rotate
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
clip newpath
restorematrix
} bind def
/GGstrk {
savematrix
newpath
normalize translate 0.0 0.0 moveto
rotate
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
restorematrix
currentlinewidth exch setlinewidth PStroke setlinewidth
} bind def
/A {
gsave
savematrix
newpath
2 index 2 div add exch 3 index 2 div sub exch
normalize 2 index 2 div sub exch 3 index 2 div add exch
translate
scale
0.0 0.0 1.0 5 3 roll arc
restorematrix
PStroke
grestore
} bind def
/Aclip {
newpath
savematrix
normalize translate 0.0 0.0 moveto
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
strokepath clip newpath
restorematrix
} bind def
/Astrk {
Gstrk
} bind def
/AA {
gsave
savematrix
newpath
3 index 2 div add exch 4 index 2 div sub exch
normalize 3 index 2 div sub exch 4 index 2 div add exch
translate
rotate
scale
0.0 0.0 1.0 5 3 roll arc
restorematrix
PStroke
grestore
} bind def
/AAclip {
savematrix
newpath
normalize translate 0.0 0.0 moveto
rotate
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath
strokepath clip newpath
restorematrix
} bind def
/AAstrk {
GGstrk
} bind def
/BEGINPRINTCODE {
/FMdicttop countdictstack 1 add def
/FMoptop count 7 sub def
/FMsaveobject save def
userdict begin
/showpage {} def
FMNORMALIZEGRAPHICS
3 index neg 3 index neg translate
} bind def
/ENDPRINTCODE {
count -1 FMoptop {pop pop} for
countdictstack -1 FMdicttop {pop end} for
FMsaveobject restore
} bind def
/gn {
0
{ 46 mul
cf read pop
32 sub
dup 46 lt {exit} if
46 sub add
} loop
add
} bind def
/cfs {
/str sl string def
0 1 sl 1 sub {str exch val put} for
str def
} bind def
/ic [
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223
0
{0 hx} {1 hx} {2 hx} {3 hx} {4 hx} {5 hx} {6 hx} {7 hx} {8 hx} {9 hx}
{10 hx} {11 hx} {12 hx} {13 hx} {14 hx} {15 hx} {16 hx} {17 hx} {18 hx}
{19 hx} {gn hx} {0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12}
{13} {14} {15} {16} {17} {18} {19} {gn} {0 wh} {1 wh} {2 wh} {3 wh}
{4 wh} {5 wh} {6 wh} {7 wh} {8 wh} {9 wh} {10 wh} {11 wh} {12 wh}
{13 wh} {14 wh} {gn wh} {0 bl} {1 bl} {2 bl} {3 bl} {4 bl} {5 bl} {6 bl}
{7 bl} {8 bl} {9 bl} {10 bl} {11 bl} {12 bl} {13 bl} {14 bl} {gn bl}
{0 fl} {1 fl} {2 fl} {3 fl} {4 fl} {5 fl} {6 fl} {7 fl} {8 fl} {9 fl}
{10 fl} {11 fl} {12 fl} {13 fl} {14 fl} {gn fl}
] def
/ms {
/sl exch def
/val 255 def
/ws cfs
/im cfs
/val 0 def
/bs cfs
/cs cfs
} bind def
400 ms
/ip {
is
0
cf cs readline pop
{ ic exch get exec
add
} forall
pop
} bind def
/rip {
bis ris copy pop
is
0
cf cs readline pop
{ ic exch get exec
add
} forall
pop pop
ris gis copy pop
dup is exch
cf cs readline pop
{ ic exch get exec
add
} forall
pop pop
gis bis copy pop
dup add is exch
cf cs readline pop
{ ic exch get exec
add
} forall
pop
} bind def
/rip4 {
kis cis copy pop
is
0
cf cs readline pop
{ ic exch get exec
add
} forall
pop pop
cis mis copy pop
dup is exch
cf cs readline pop
{ ic exch get exec
add
} forall
pop pop
mis yis copy pop
dup dup add is exch
cf cs readline pop
{ ic exch get exec
add
} forall
pop pop
yis kis copy pop
3 mul is exch
cf cs readline pop
{ ic exch get exec
add
} forall
pop
} bind def
/wh {
/len exch def
/pos exch def
ws 0 len getinterval im pos len getinterval copy pop
pos len
} bind def
/bl {
/len exch def
/pos exch def
bs 0 len getinterval im pos len getinterval copy pop
pos len
} bind def
/s1 1 string def
/fl {
/len exch def
/pos exch def
/val cf s1 readhexstring pop 0 get def
pos 1 pos len add 1 sub {im exch val put} for
pos len
} bind def
/hx {
3 copy getinterval
cf exch readhexstring pop pop
} bind def
/wbytes {
dup dup
8 gt { pop 8 idiv mul }
{ 8 eq {pop} {1 eq {7 add 8 idiv} {3 add 4 idiv} ifelse} ifelse } ifelse
} bind def
/BEGINBITMAPBWc {
1 {} COMMONBITMAPc
} bind def
/BEGINBITMAPGRAYc {
8 {} COMMONBITMAPc
} bind def
/BEGINBITMAP2BITc {
2 {} COMMONBITMAPc
} bind def
/COMMONBITMAPc {
/cvtProc exch def
/depth exch def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/lb width depth wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
cvtProc
/is im 0 lb getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
width height depth [width 0 0 height neg 0 height]
{ip} image
bitmapsave restore
grestore
} bind def
/BEGINBITMAPBW {
1 {} COMMONBITMAP
} bind def
/BEGINBITMAPGRAY {
8 {} COMMONBITMAP
} bind def
/BEGINBITMAP2BIT {
2 {} COMMONBITMAP
} bind def
/COMMONBITMAP {
/cvtProc exch def
/depth exch def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/bitmapsave save def
cvtProc
/is width depth wbytes string def
/cf currentfile def
width height depth [width 0 0 height neg 0 height]
{cf is readhexstring pop} image
bitmapsave restore
grestore
} bind def
/ngrayt 256 array def
/nredt 256 array def
/nbluet 256 array def
/ngreent 256 array def
fMLevel1 {
/colorsetup {
currentcolortransfer
/gryt exch def
/blut exch def
/grnt exch def
/redt exch def
0 1 255 {
/indx exch def
/cynu 1 red indx get 255 div sub def
/magu 1 green indx get 255 div sub def
/yelu 1 blue indx get 255 div sub def
/kk cynu magu min yelu min def
/u kk currentundercolorremoval exec def
% /u 0 def
nredt indx 1 0 cynu u sub max sub redt exec put
ngreent indx 1 0 magu u sub max sub grnt exec put
nbluet indx 1 0 yelu u sub max sub blut exec put
ngrayt indx 1 kk currentblackgeneration exec sub gryt exec put
} for
{255 mul cvi nredt exch get}
{255 mul cvi ngreent exch get}
{255 mul cvi nbluet exch get}
{255 mul cvi ngrayt exch get}
setcolortransfer
{pop 0} setundercolorremoval
{} setblackgeneration
} bind def
}
{
/colorSetup2 {
[ /Indexed /DeviceRGB 255
{dup red exch get 255 div
exch dup green exch get 255 div
exch blue exch get 255 div}
] setcolorspace
} bind def
} ifelse
/fakecolorsetup {
/tran 256 string def
0 1 255 {/indx exch def
tran indx
red indx get 77 mul
green indx get 151 mul
blue indx get 28 mul
add add 256 idiv put} for
currenttransfer
{255 mul cvi tran exch get 255.0 div}
exch fmConcatProcs settransfer
} bind def
/BITMAPCOLOR {
/depth 8 def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/bitmapsave save def
fMLevel1 {
colorsetup
/is width depth wbytes string def
/cf currentfile def
width height depth [width 0 0 height neg 0 height]
{cf is readhexstring pop} {is} {is} true 3 colorimage
} {
colorSetup2
/is width depth wbytes string def
/cf currentfile def
7 dict dup begin
/ImageType 1 def
/Width width def
/Height height def
/ImageMatrix [width 0 0 height neg 0 height] def
/DataSource {cf is readhexstring pop} bind def
/BitsPerComponent depth def
/Decode [0 255] def
end image
} ifelse
bitmapsave restore
grestore
} bind def
/BITMAPCOLORc {
/depth 8 def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/lb width depth wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
fMLevel1 {
colorsetup
/is im 0 lb getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
width height depth [width 0 0 height neg 0 height]
{ip} {is} {is} true 3 colorimage
} {
colorSetup2
/is im 0 lb getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
7 dict dup begin
/ImageType 1 def
/Width width def
/Height height def
/ImageMatrix [width 0 0 height neg 0 height] def
/DataSource {ip} bind def
/BitsPerComponent depth def
/Decode [0 255] def
end image
} ifelse
bitmapsave restore
grestore
} bind def
/BITMAPTRUECOLORc {
/depth 24 def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/lb width depth wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
/is im 0 lb getinterval def
/ris im 0 width getinterval def
/gis im width width getinterval def
/bis im width 2 mul width getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{width rip pop ris} {gis} {bis} true 3 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPCMYKc {
/depth 32 def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/lb width depth wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
/is im 0 lb getinterval def
/cis im 0 width getinterval def
/mis im width width getinterval def
/yis im width 2 mul width getinterval def
/kis im width 3 mul width getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{width rip4 pop cis} {mis} {yis} {kis} true 4 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPTRUECOLOR {
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/bitmapsave save def
/is width string def
/gis width string def
/bis width string def
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{ cf is readhexstring pop }
{ cf gis readhexstring pop }
{ cf bis readhexstring pop }
true 3 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPCMYK {
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/bitmapsave save def
/is width string def
/mis width string def
/yis width string def
/kis width string def
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{ cf is readhexstring pop }
{ cf mis readhexstring pop }
{ cf yis readhexstring pop }
{ cf kis readhexstring pop }
true 4 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPTRUEGRAYc {
/depth 24 def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/lb width depth wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
/is im 0 lb getinterval def
/ris im 0 width getinterval def
/gis im width width getinterval def
/bis im width 2 mul width getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{width rip pop ris gis bis width gray} image
bitmapsave restore
grestore
} bind def
/BITMAPCMYKGRAYc {
/depth 32 def
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/lb width depth wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
/is im 0 lb getinterval def
/cis im 0 width getinterval def
/mis im width width getinterval def
/yis im width 2 mul width getinterval def
/kis im width 3 mul width getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{width rip pop cis mis yis kis width cgray} image
bitmapsave restore
grestore
} bind def
/cgray {
/ww exch def
/k exch def
/y exch def
/m exch def
/c exch def
0 1 ww 1 sub { /i exch def c i get m i get y i get k i get CMYKtoRGB
.144 mul 3 1 roll .587 mul 3 1 roll .299 mul add add
c i 3 -1 roll floor cvi put } for
c
} bind def
/gray {
/ww exch def
/b exch def
/g exch def
/r exch def
0 1 ww 1 sub { /i exch def r i get .299 mul g i get .587 mul
b i get .114 mul add add r i 3 -1 roll floor cvi put } for
r
} bind def
/BITMAPTRUEGRAY {
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/bitmapsave save def
/is width string def
/gis width string def
/bis width string def
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{ cf is readhexstring pop
cf gis readhexstring pop
cf bis readhexstring pop width gray} image
bitmapsave restore
grestore
} bind def
/BITMAPCMYKGRAY {
gsave
3 index 2 div add exch
4 index 2 div add exch
translate
rotate
1 index 2 div neg
1 index 2 div neg
translate
scale
/height exch def /width exch def
/bitmapsave save def
/is width string def
/yis width string def
/mis width string def
/kis width string def
/cf currentfile def
width height 8 [width 0 0 height neg 0 height]
{ cf is readhexstring pop
cf mis readhexstring pop
cf yis readhexstring pop
cf kis readhexstring pop width cgray} image
bitmapsave restore
grestore
} bind def
/BITMAPGRAY {
8 {fakecolorsetup} COMMONBITMAP
} bind def
/BITMAPGRAYc {
8 {fakecolorsetup} COMMONBITMAPc
} bind def
/ENDBITMAP {
} bind def
end
/ALDmatrix matrix def ALDmatrix currentmatrix pop
/StartALD {
/ALDsave save def
savematrix
ALDmatrix setmatrix
} bind def
/InALD {
restorematrix
} bind def
/DoneALD {
ALDsave restore
} bind def
/I { setdash } bind def
/J { [] 0 setdash } bind def
%%EndProlog
%%BeginSetup
(5.0) FMVERSION
1 1 0 0 612 792 0 1 7 FMDOCUMENT
0 0 /Times-Roman FMFONTDEFINE
1 0 /Times-Italic FMFONTDEFINE
2 0 /Times-Bold FMFONTDEFINE
3 0 /Helvetica-Bold FMFONTDEFINE
4 0 /Times-BoldItalic FMFONTDEFINE
32 FMFILLS
0 0 FMFILL
1 0.1 FMFILL
2 0.3 FMFILL
3 0.5 FMFILL
4 0.7 FMFILL
5 0.9 FMFILL
6 0.97 FMFILL
7 1 FMFILL
8 <0f1e3c78f0e1c387> FMFILL
9 <0f87c3e1f0783c1e> FMFILL
10 FMFILL
11 FMFILL
12 <8142241818244281> FMFILL
13 <03060c183060c081> FMFILL
14 <8040201008040201> FMFILL
16 1 FMFILL
17 0.9 FMFILL
18 0.7 FMFILL
19 0.5 FMFILL
20 0.3 FMFILL
21 0.1 FMFILL
22 0.03 FMFILL
23 0 FMFILL
24 FMFILL
25 FMFILL
26 <3333333333333333> FMFILL
27 <0000ffff0000ffff> FMFILL
28 <7ebddbe7e7dbbd7e> FMFILL
29 FMFILL
30 <7fbfdfeff7fbfdfe> FMFILL
%%EndSetup
%%Page: "23" 1
%%BeginPaperSize: Letter
%%EndPaperSize
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
J
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 23 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
(ceton University Press, 1970.) 126 712 T
([Pe76]) 72 690 T
(Pedoe, D.,) 126 690 T
1 F
(Geometry and the Liberal Arts,) 178.99 690 T
0 F
( Penguin Books, Inc., 1976.) 329.32 690 T
([Pe1819]) 72 668 T
(Peyrard, F.,) 126 668 T
1 F
(Les Oeuvres D\325Euclide, Traduites Litteralment) 184.99 668 T
0 F
(, C. F. Patris, Paris, 1819.) 411.31 668 T
([Pl1831]) 72 646 T
0.75 (Playfair, J.,) 126 646 P
1 F
0.75 (Elements of Geometry; Containing the First Six Books of Euclid) 185.15 646 P
0 F
0.75 (, Bell &) 500.17 646 P
(Bradfute, Edinburgh, 1831.) 126 632 T
([PS85]) 72 610 T
-0.39 (Preparata, F. P. and Shamos, M. I.,) 126 610 P
1 F
-0.39 (Computational Geometry: An Introduction,) 293.91 610 P
0 F
-0.39 ( Spring-) 501.39 610 P
(er-Verlag, 1985.) 126 596 T
([Ru51]) 72 574 T
1.85 (Russell, B.,) 126 574 P
1 F
1.85 (The Autobiography of Bertrand Russell) 188.04 574 P
0 F
1.85 (, Little, Brown & Co., Boston,) 384.76 574 P
(1951.) 126 560 T
([Sh28]) 72 538 T
0.29 (Shenton, W. F., "The first English Euclid,") 126 538 P
1 F
0.29 (American Mathematical Monthly) 337.18 538 P
0 F
0.29 (, vol. 35,) 497.08 538 P
(1928, pp. 505-511.) 126 524 T
([SA48]) 72 502 T
0.85 (Stark, M. E. and Archibald, R. C., "Jacob Steiner\325s geometrical constructions with a) 126 502 P
0.58 (ruler given a fixed circle with its center," \050translated from the German 1833 edition\051,) 126 488 P
1 F
(Scripta Mathematica) 126 474 T
0 F
(, vol. 14, 1948, pp. 189-264.) 226.99 474 T
([Sm1879]) 72 452 T
(Smith, J. H.,) 126 452 T
1 F
(Elements of Geometry) 189.01 452 T
0 F
(, Rivingtons, Waterloo Place, London, 1879.) 295.66 452 T
([Sm61]) 72 430 T
-0.17 (Smogorzhevskii, A. S.,) 126 430 P
1 F
-0.17 (The Ruler in Geometrical Constructions,) 239.84 430 P
0 F
-0.17 ( Blaisdell, New York,) 435.51 430 P
(1961.) 126 416 T
([Ta1895]) 72 394 T
(Taylor, H. M.,) 126 394 T
1 F
(Euclid\325s Elements of Geometry) 198.32 394 T
0 F
(, Cambridge University Press, 1895.) 347.96 394 T
([To1876]) 72 372 T
(Todhunter, I.,) 126 372 T
1 F
(The Elements of Euclid) 194.99 372 T
0 F
(, Copp, Clarck & Co., Toronto, 1876.) 306.65 372 T
([To84]) 72 350 T
0.1 (Toussaint, G. T., "Computational geometric thinking as kinesthetic thinking,") 126 350 P
1 F
0.1 (Confer-) 502.67 350 P
(ence on Thinking,) 126 336 T
0 F
(Harvard University, August 1984.) 214.66 336 T
([Wi1703]) 72 314 T
-0.56 (Williams, R.,) 126 314 P
1 F
-0.56 (Elements of Euclid Explained and Demonstrated in a New and Most Easy) 191.88 314 P
(Method) 126 300 T
0 F
(, Globemaker, London, 1703.) 162.66 300 T
FMENDPAGE
%%EndPage: "23" 1
%%Page: "22" 2
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 22 -) 293 36 T
72 72 540 720 R
7 X
V
1 F
0 X
(From the Greek,) 126 712 T
0 F
( Franz Steiner Verlag Wiesbaden GMBH, Stuttgart, 1987.) 205.64 712 T
([Cl1654]) 72 690 T
(Clavio, C.,) 126 690 T
1 F
(Euclidis Elementorum) 181.01 690 T
0 F
(, Jonae Rosae, Francofurti, 1654.) 288 690 T
([CR81]) 72 668 T
(Courant, R. and Robbins, H.,) 126 668 T
1 F
(What is Mathematics?) 268.67 668 T
0 F
(Oxford University Press, 1981.) 379 668 T
([Du90]) 72 646 T
1.4 (Dunham, W.,) 126 646 P
1 F
1.4 (Journey Through Genius: The Great Theorems of Mathematics,) 196.46 646 P
0 F
1.4 ( John) 512.93 646 P
(Wiley & Sons, Inc., 1990.) 126 632 T
([Di55]) 72 610 T
0.03 (Dijksterhuis, E. J.,) 126 610 P
1 F
0.03 (The First Book of Euclid\325s Elementa) 217.74 610 P
0 F
0.03 (, E. J. Brill, Leiden, The Neth-) 393.53 610 P
(erlands, 1955.) 126 596 T
([Ha1041]) 72 574 T
0.18 (Ibn al-Haytham,) 126 574 P
1 F
0.18 (On the Resolution of Doubts in Euclid\325s Elements and Interpretation) 208.02 574 P
-0.24 (of Its Special Meanings,) 126 560 P
0 F
-0.24 ( University of Istanbul, 1041 A.D., facsimile edition published) 241.27 560 P
-0.69 (by the Institute for the History of Arabic-Islamic Science at the Johan Wolfgang Goethe) 126 546 P
(University, Frankfurt am Main, 1985.) 126 532 T
([He1883]) 72 510 T
(Heiberg, I. L.,) 126 510 T
1 F
(Euclidis Elementa) 196.98 510 T
0 F
(, B. G. Teubneri, Lipsiae, 1883.) 284.64 510 T
([He28]) 72 488 T
-0.66 (Heath, Sir T. L.,) 126 488 P
1 F
-0.66 (The Thirteen Books of Euclid\325s Elements,) 204.67 488 P
0 F
-0.66 (Cambridge University Press,) 403 488 P
(1928.) 126 474 T
([Kl39]) 72 452 T
1.01 (Klein, F.,) 126 452 P
1 F
1.01 (Elementary Mathematics from an Advanced Standpoint: Geometry) 176.35 452 P
0 F
1.01 (, Dover) 503.01 452 P
(Publications, Inc., 1939.) 126 438 T
([Ho70]) 72 416 T
(Honsberger, R.,) 126 416 T
1 F
(Ingenuity in Mathematics,) 204.98 416 T
0 F
( Random House, Inc., 1970.) 330.64 416 T
([Ka78]) 72 394 T
0.01 (Kayas, G. J.,) 126 394 P
1 F
0.01 (Euclide: Les Elements) 190.34 394 P
0 F
0.01 (, Editions du Centre National de la Recherche Sci-) 297.66 394 P
(entifique, Paris 1978.) 126 380 T
([Ko86]) 72 358 T
2.62 (Kostovskii, A.,) 126 358 P
1 F
2.62 (Geometrical Constructions with Compasses Only,) 206.92 358 P
0 F
2.62 ( Mir Publishers,) 457.75 358 P
(Moscow, 1986.) 126 344 T
([HS1887]) 72 322 T
0.19 (Hall, H. S. and Stevens, F. H.,) 126 322 P
1 F
0.19 (A Text-Book of Euclid\325s Elements) 275.35 322 P
0 F
0.19 (, Macmillan and Co.,) 438.09 322 P
(London, 1887.) 126 308 T
([La41]) 72 286 T
-0.57 (Langer, R. E., "Alexandria - Shrine of mathematics,") 126 286 P
1 F
-0.57 (American Mathematical Monthly) 378.83 286 P
0 F
-0.57 (,) 537 286 P
(vol. 48, 1941, pp. 109-125.) 126 272 T
([La1861]) 72 250 T
-0.6 (Lardner, D.,) 126 250 P
1 F
-0.6 (The First Six Books of the Elements of Euclid,) 186.45 250 P
0 F
-0.6 ( H. G. Bohn, Covent Garden,) 402.67 250 P
(London, 1861.) 126 236 T
([Le02]) 72 214 T
(Lemoine, E.,) 126 214 T
1 F
(Geometrographie,) 190.99 214 T
0 F
(C. Naud, Paris, 1902.) 282.31 214 T
([Ma1797]) 72 192 T
(Mascheroni, L.,) 126 192 T
1 F
(The Geometry of Compasses,) 204.98 192 T
0 F
(University of Pavia, 1797.) 348.64 192 T
([Mo1672]) 72 170 T
(Mohr, G.,) 126 170 T
1 F
(The Danish Euclid) 176.33 170 T
0 F
(, Amsterdam, 1672.) 266.33 170 T
([Mo70]) 72 148 T
0.1 (Morrow, G. R.,) 126 148 P
1 F
0.1 (Proclus: A Commentary on the First Book of Euclid\325s Elements,) 203.31 148 P
0 F
0.1 ( Prin-) 512.9 148 P
FMENDPAGE
%%EndPage: "22" 2
%%Page: "21" 3
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 21 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
-0.54 (of Greek mathematics. The work presented here suggests a new way of examining old constructive) 72 712 P
(mathematics and a new way for historians of mathematics and philologists to do their research.) 72 698 T
-0.73 (The work presented here also has implications for education. It has already been argued that) 108 676 P
1.19 (Euclidean construction problems provide an excellent method of teaching high school students) 72 662 P
0.2 (constructive proofs of existence theorems [Av89]. The work presented here suggests that Euclid-) 72 648 P
-0.04 (ean constructive geometry can be used as an ideal medium for teaching many of the most modern) 72 634 P
-0.28 (concepts concerning the design and analysis of algorithms, to high school students. For easy prob-) 72 620 P
0.18 (lems the students can prove that Euclid\325s constructions are valid for all possible inputs. For more) 72 606 P
-0.18 (difficult problems they can search for constructions that require fewer steps. Finally, for real chal-) 72 592 P
(lenging problems they can search for constructions that require the fewest number of steps.) 72 578 T
2 14 Q
(10.) 72 526.67 T
(Acknowledgment) 108 526.67 T
0 12 Q
0.78 (The author is grateful to Hossam ElGindy for translating Ibn al-Haytham\325s 11th century) 108 504 P
-0.36 (Arabic manuscript [Ha1041], to Mariza Komioti for translating Heiberg\325s definitive Greek edition) 72 490 P
-0.43 ([Ka78], to Kelly Lyons for bringing to his attention a copy of Peyrard\325s book at Queens University) 72 476 P
0.29 ([Pe1819], to Diane Souvaine, Sue Whitesides and Chee Yap for discussions on this topic as well) 72 462 P
(as to Arnon Avron for providing some useful references.) 72 448 T
2 14 Q
(11.) 72 396.67 T
(References) 108 396.67 T
0 12 Q
([AHU74]) 72 374 T
0.54 (Aho, A. V., Hopcroft, J. E. and Ullman, J. D.,) 126 374 P
1 F
0.54 (The Design and Analysis of Computer) 354.32 374 P
(Algorithms,) 126 360 T
0 F
(Addison-Wesley, 1974.) 185.34 360 T
([Ar50]) 72 338 T
2.65 (Archibald, R. C., "The first translation of Euclid\325s elements into English and its) 126 338 P
(source,") 126 324 T
1 F
(American Mathematical Monthly,) 168.22 324 T
0 F
( vol. 57, 1950, pp. 443-452.) 330.53 324 T
([Av87]) 72 302 T
1.51 (Avron, A., "Theorems on strong constructibility with a compass alone,") 126 302 P
1 F
1.51 (Journal of) 488.83 302 P
(Geometry) 126 288 T
0 F
(, vol. 30, 1987, pp. 28-35.) 173.32 288 T
([Av89]) 72 266 T
0.32 (Avron, A., "Construction problems - why and how?") 126 266 P
1 F
0.32 (International Journal of Educa-) 385.36 266 P
(tion in Science and Technology) 126 252 T
0 F
(, vol. 20, No. 2, 1989, pp. 273-287.) 276.65 252 T
([Av90]) 72 230 T
0.91 (Avron, A., "On strict strong constructibility with a compass alone,") 126 230 P
1 F
0.91 (Journal of Geo-) 461.53 230 P
(metry,) 126 216 T
0 F
( vol. 38, 1990, pp. 12-15.) 156.32 216 T
([Ba1705]) 72 194 T
(Barrow, I.,) 126 194 T
1 F
(Euclide\325s Elements) 180.98 194 T
0 F
(, E. Redmayne, London, 1705.) 273.3 194 T
([Be71]) 72 172 T
(Beckman, P.,) 126 172 T
1 F
(A History of Pi) 193 172 T
0 F
(, The Golem Press, New York, 1971.) 265.33 172 T
([Bu83]) 72 150 T
-0.42 (Busard, H. L. L.,) 126 150 P
1 F
-0.42 (The First Latin Translation of Euclid\325s Elements Commonly Ascribed) 208.66 150 P
(to Adelard of Bath) 126 136 T
0 F
(, Pontifical Institute of Medieval Studies, 1983.) 215 136 T
([Bu84]) 72 114 T
1.18 (Busard, H. L. L.,) 126 114 P
1 F
1.18 (The Latin Translation of the Arabic Version of Euclid\325s) 215.04 114 P
0 F
1.18 (Elements) 495.34 114 P
1 F
-0.52 (Commonly Ascribed to Gerard de Cremona) 126 100 P
0 F
-0.52 (, E. J. Brill, Leiden, The Netherlands, 1984.) 333.69 100 P
([Bu87]) 72 78 T
0.09 (Busard, H. L. L.,) 126 78 P
1 F
0.09 (The Medieval Latin Translation of Euclid\325s) 210.66 78 P
0 F
0.09 (Elements) 422.52 78 P
1 F
0.09 ( Made Directly) 467.18 78 P
FMENDPAGE
%%EndPage: "21" 3
%%Page: "20" 4
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 20 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
(tion presented also in Pedoe [Pe76].) 72 712 T
2 F
(Algorithm) 108 690 T
(CO:) 164.33 690 T
0 F
( [Compass Only version]) 186.32 690 T
2 F
-0.58 (Input:) 108 668 P
0 F
-0.58 (Let A be the given point, and BC the given straight line. {Thus it is required to place) 143.1 668 P
-0.28 (at the point A \050as an extremity\051 a straight line equal to the given straight line BC.} See Fig.) 108 654 P
(8.2.) 108 640 T
2 F
(Begin) 108 618 T
1 F
(Step 1) 108 596 T
0 F
(:) 137.66 596 T
(Draw a circle with center A and radius AB.) 153 596 T
1 F
(Step 2) 108 574 T
0 F
(:) 137.66 574 T
(Draw a circle with center B and radius BA. {the two circles intersect at D and E.) 153 574 T
1 F
(Step) 108 552 T
0 F
(3:) 131.66 552 T
(Draw a circle with center D and radius DC.) 153 552 T
1 F
(Step) 108 530 T
0 F
(4:) 131.66 530 T
(Draw a circle with center E and radius EC.) 153 530 T
0.34 (These two circles intersect at C and X where X is the desired reflection point of C across) 108 508 P
(the imaginary line through DE and XA is the desired length.) 108 494 T
2 F
(End) 108 472 T
0 F
-0.25 (In the spirit of Proclus we invite the reader to supply the proofs of correctness of the above) 108 428 P
(two constructions.) 72 414 T
2 14 Q
(9.) 72 384.67 T
(Conclusions) 108 384.67 T
0 12 Q
-0.57 (We mention in closing that even the 20th century) 108 362 P
2 F
-0.57 (Algorithm) 342.52 362 P
-0.57 (CO) 398.29 362 P
0 F
-0.57 ( pales by comparison with) 416.29 362 P
2 F
-0.07 (Algorithm) 72 348 P
-0.07 (Euclid) 128.26 348 P
0 F
-0.07 (from the point of view of robustness with respect to singularities. Consider for) 164.54 348 P
-0.04 (example the case where point A happens to lie at a location equidistant from B and C.) 72 334 P
2 F
-0.04 (Algorithm) 486.67 334 P
-0.43 (Euclid) 72 320 P
0 F
-0.43 ( executes in this case as easily as in any other since everything is well defined. Without spe-) 105.35 320 P
-0.28 (cial flag-waving code however) 72 306 P
2 F
-0.28 (Algorithm CO) 222.17 306 P
0 F
-0.28 ( could crash attempting to draw a circle with radius) 296.22 306 P
(zero and then intersecting two circles one of which has radius zero.) 72 292 T
0.42 (One apparent difference between modern and classical computational geometry concerns) 108 270 P
-0.64 (the issue of lower bounds on the complexity of geometric problems. Although Lemoine [Le02] and) 72 256 P
-0.12 (others were concerned with defining primitive operations and counting the number of such opera-) 72 242 P
-0.04 (tions involved in a construction they did not ever appear to have considered the question of deter-) 72 228 P
0.81 (mining the minimum number of operations required to solve a given problem under a specified) 72 214 P
0.02 (model of computation. For example, if we define 1\051 drawing a line and 2\051 drawing a circle, as the) 72 200 P
0.81 (primitive operations allowed under the straight edge and compass model of computation,) 72 186 P
2 F
0.81 (Algo-) 512 186 P
0.03 (rithm Euclid) 72 172 P
0 F
0.03 (takes nine steps,) 140.73 172 P
2 F
0.03 (Algorithm MS) 222.13 172 P
0 F
0.03 (takes six steps whereas) 299.51 172 P
2 F
0.03 (Algorithm CO) 413.6 172 P
0 F
0.03 ( takes only) 487.95 172 P
0.11 (four steps. Its non robustness not withstanding, is) 72 158 P
2 F
0.11 (Algorithm CO) 312.9 158 P
1 F
0.11 (optimal) 390.46 158 P
0 F
0.11 (? In other words is four) 427.13 158 P
-0.12 (a lower bound on this problem? Is) 72 144 P
2 F
-0.12 (Algorithm Euclid) 238.11 144 P
0 F
-0.12 (the optimal) 330.54 144 P
1 F
-0.12 (robust) 387.62 144 P
0 F
-0.12 ( algorithm? It is not diffi-) 418.29 144 P
-0.27 (cult to argue that at least three steps are required. We conjecture that in fact four are always neces-) 72 130 P
(sary.) 72 116 T
-0.28 (This research suggests that perhaps the chaotic situation described here with respect to Eu-) 108 94 P
0.43 (clid\325s second proposition exists also for his other propositions involving cases and indeed for all) 72 80 P
FMENDPAGE
%%EndPage: "20" 4
%%Page: "19" 5
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 19 -) 293 36 T
72 72 540 495 R
7 X
V
0 X
(and radius BA.) 153 487 T
1 F
(Step 3) 108 465 T
0 F
(:) 137.66 465 T
-0.31 (Draw a line L through the intersection points D and E of the two circles produced) 153 465 P
(in steps 1 and 2.) 153 451 T
1 F
(Step 4) 108 429 T
0 F
(:) 137.66 429 T
(Draw a circle with center C that intersects line L at points F and G.) 153 429 T
1 F
(Step 5) 108 407 T
0 F
(:) 137.66 407 T
(Draw a circle with center G and radius GC.) 153 407 T
1 F
(Step 6) 108 385 T
0 F
(:) 137.66 385 T
(Draw a circle with center F and radius FC.) 153 385 T
-0.25 (These two circles intersect at C and H where H is the desired reflection point of C across L) 108 363 P
(and HA the desired segment.) 108 349 T
2 F
(End) 108 327 T
0 F
-0.09 (Recall that in 1672 Jorg Mohr and in 1797 the Italian geometer Lorenzo Mascheroni inde-) 108 283 P
0.05 (pendently proved that any construction that can be carried out with a straight edge and a compass) 72 269 P
-0.13 (can be carried out with a compass alone. The reader may wonder how on earth we can draw a line) 72 255 P
0.06 (segment of length BC with one extremity at A) 72 241 P
1 F
0.06 (without) 297.56 241 P
0 F
0.06 ( using a straight edge. Strictly speaking we) 333.57 241 P
0.21 (cannot and therefore in constructions with compasses alone we require only that in order to draw) 72 227 P
-0.1 (a line or line segment two points on the line or the two endpoints of the line segment be specified.) 72 213 P
-0.57 (Such a pair of points clearly specifies a line or line segment, as the case may be, in an unambiguous) 72 199 P
0.67 (manner. Thus we are actually) 72 185 P
1 F
0.67 (simulating) 219.97 185 P
0 F
0.67 ( a line or line segment by two points. In this sense it is) 270.64 185 P
0.29 (more appropriate to state the Mohr-Mascheroni theorem as:) 72 171 P
1 F
0.29 (any construction that can be carried) 363.58 171 P
0.47 (out with a straight edge and a compass can be) 72 157 P
0 F
0.47 (simulated) 302.72 157 P
1 F
0.47 ( with a compass alone) 349.39 157 P
0 F
0.47 (. The above con-) 457.94 157 P
0.08 (struction based on the principle of mirror symmetry uses both a straight edge and a compass. It is) 72 143 P
-0.35 (fitting to end this discussion by presenting a construction, also based on the mirror symmetry prin-) 72 129 P
-0.49 (ciple, that uses a compass only. We present the one described in [Ho70] which is the first construc-) 72 115 P
288 495 540 720 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
342 504 504 531 R
7 X
0 0 0 1 0 0 0 K
V
0 12 Q
0 X
0.2 (Fig. 8.2 Illustrating the construc-) 342 523 P
(tion with compasses only.) 342 509 T
90 450 2 2 396 598 G
0.5 H
0 Z
90 450 2 2 396 598 A
3 9 Q
(A) 385 595 T
(B) 434 590 T
(C) 486 645 T
(E) 411 555 T
(D) 410 635 T
(X) 334 647 T
0 0 612 792 C
432 598 484 643 2 L
3 H
2 Z
0 X
0 0 0 1 0 0 0 K
N
0.5 H
0 Z
90 450 36 36 432 598 A
90 450 36 36 396 598 A
2 Z
0 90 72 72.5 414 629.5 A
90 180 72 72.5 414 629.5 A
0 90 108 108 414 562 A
90 180 108 108 414 562 A
72 495 288 720 R
7 X
V
1 12 Q
0 X
(straight line.) 189 712 T
2 F
(Algorithm) 108 690 T
(MS:) 164.33 690 T
0 F
10.01 ([Mirror Symmetry) 189 690 P
(version]) 189 676 T
2 F
0.57 (Input:) 108 654 P
0 F
0.57 (Let A be the given point, and) 144.25 654 P
0.03 (BC the given straight line. {Thus it is) 108 640 P
-0.08 (required to place at the point A \050as an) 108 626 P
0.45 (extremity\051 a straight line equal to the) 108 612 P
(given straight line BC.} See Fig. 8.1.) 108 598 T
2 F
(Begin) 108 576 T
1 F
(Step 1) 108 554 T
0 F
(:) 137.66 554 T
0.41 (Draw a circle with center A) 153 554 P
(and radius AB.) 153 540 T
1 F
(Step 2) 108 518 T
0 F
(:) 137.66 518 T
0.54 (Draw a circle with center B) 153 518 P
FMENDPAGE
%%EndPage: "19" 5
%%Page: "18" 6
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 18 -) 293 36 T
72 72 540 432 R
7 X
V
0 X
(than the French version and is in agreement with the correct algorithms discussed earlier.) 72 424 T
-0.02 (In conclusion, it is ironic that in Kayas\325 translation the desire to be true to the spirit of Eu-) 108 402 P
-0.31 (clid leads him on the road to betray Euclid. This suggests that although literal translations may fail) 72 388 P
-0.68 (miserably for poetry they may be essential for mathematics and computer science. The best remedy) 72 374 P
(however is for the translator to possess an understanding of the deep structure of the proof.) 72 360 T
2 14 Q
(8.) 72 330.67 T
(Late 20th Century Algorithms) 108 330.67 T
0 12 Q
-0.64 (For the sake of comparison, contrast and completeness we offer in this section two alternate) 108 308 P
-0.33 (modern constructions that are fundamentally different from all those considered by Euclid, Heron,) 72 294 P
-0.49 (Proclus and the other Greek and subsequent commentators as well as the plethora of 19th and early) 72 280 P
(20th century text-book writers. These are based on the notion of) 72 266 T
1 F
(mirror symmetry.) 382.61 266 T
0 F
-0.22 (As before let A be the given point and let BC be the desired length to be transferred so that) 108 244 P
-0.12 (A is at an extremity. Without loss of generality let B be the chosen extremity and refer to Fig. 8.1.) 72 230 P
-0.46 (The idea is to first construct a line L that perpendicularly bisects the segment AB and subsequently) 72 216 P
-0.35 (perform a mirror symmetry transformation of the segment BC with line L as the axis of symmetry.) 72 202 P
-0.33 (Note that A and C may or may not be on the same side of L depending on the particular case of the) 72 188 P
0.3 (input configuration at hand. In either case we reflect C about L to obtain our desired result. Note) 72 174 P
0.39 (also that Euclid\325s construction does not necessarily yield a transferred length that is symmetrical) 72 160 P
(about L.) 72 146 T
2 F
(Proposition 2:) 108 124 T
1 F
-0.22 (To place at a given point) 189 124 P
0 F
-0.22 (\050) 310.34 124 P
1 F
-0.22 (as an extremity) 314.33 124 P
0 F
-0.22 (\051) 387.21 124 P
1 F
-0.22 ( a straight line equal to a given) 391.21 124 P
72 432 306 720 R
7 X
V
0 X
(of the text.) 108 712 T
0 F
0.09 (Accordingly, this French translation con-) 108 690 P
0 (tains the following description of) 72 676 P
1 F
0 (Step 3) 234.35 676 P
0 F
0 ( [refer to) 264.02 676 P
2 F
1.22 (Algorithm Euclid) 72 662 P
0 F
1.22 ( and Fig. 4.1] \322) 162.9 662 P
1 F
1.22 (Prolongeons) 244.67 662 P
0.29 (DA suivant AE et BD suivant BF.\323) 72 648 P
0 F
0.29 (This literally) 244.04 648 P
1.67 (means \322Extend DA following AE and BD fol-) 72 634 P
0.37 (lowing BF.\323 Note that the first half of this state-) 72 620 P
-0.33 (ment \050extend DA and BD\051 is ambiguous and rep-) 72 606 P
0.15 (resents a step towards agreement with the phras-) 72 592 P
-0.63 (ing of the texts of the 17th, 18th and 19th Century) 72 578 P
1.06 (English texts. The complete statement is never-) 72 564 P
0.05 (theless saved by explicitly mentioning the A and) 72 550 P
-0.48 (B in AE and BD, respectively. One can easily en-) 72 536 P
-0.33 (vision these references to A and B being dropped) 72 522 P
(during the next translation.) 72 508 T
2.12 (A) 108 486 P
1 F
2.12 (literal) 121.78 486 P
0 F
2.12 ( translation of the same Greek) 151.12 486 P
0.55 (text yielded the following for) 72 472 P
1 F
0.55 (Step. 3:) 218.37 472 P
0 F
0.55 (\322) 259.12 472 P
1 F
0.55 (Let lines) 264.45 472 P
1.38 (AE, BF emerge outwards colinear to lines DA,) 72 458 P
0.1 (DB.\323) 72 444 P
0 F
0.1 (Note that this is considerably more precise) 100.77 444 P
315 441 540 720 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
315 441 540 720 R
7 X
0 0 0 1 0 0 0 K
V
0.5 H
2 Z
0 X
180 270 86.5 86.5 428.5 665.5 A
354 621 408 558 2 L
1 H
10 X
N
0.5 H
0 X
0 90 43 43 407 558 A
270 360 48.5 43 401.5 558 A
90 180 43 43 450 558 A
180 270 43 43 450 558 A
450 558 504 621 2 L
3 H
N
429 698 429 493 2 L
1 H
11 X
N
0.5 H
0 X
180 270 97 97.5 515 622.5 A
270 360 86.5 86.5 428.5 665.5 A
90 180 86.5 86.5 428.5 579.5 A
0 90 86.5 86.5 428.5 579.5 A
353 623 504 623 2 L
10 X
N
0 X
90 180 97 97.5 515 622.5 A
324 450 522 477 R
7 X
V
0 12 Q
0 X
(Fig. 8.1 Illustrating the mirror symmetry) 324 469 T
(method for solving proposition 2.) 324 455 T
3 9 Q
(A) 395 555 T
90 450 3 3 407 558 G
0 Z
90 450 3 3 407 558 A
(B) 454 548 T
(C) 510 620 T
(L) 420 696 T
(D) 431 602 T
(E) 432 506 T
(G) 418 671 T
(F) 420 569 T
(H) 342 618 T
0 0 612 792 C
FMENDPAGE
%%EndPage: "18" 6
%%Page: "17" 7
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 17 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
(but the proofs are very often replaced by instructions for proofs or outlines of proofs.\323) 72 712 T
(Adelard of Bath writes) 108 690 T
1 F
(Step 3) 220.64 690 T
0 F
( as follows:) 250.31 690 T
(\322) 108 668 T
1 F
(Protrahanturque linee DA et DB directe usque ad L et G.\323) 113.33 668 T
0 F
0.38 (His actual letters are different and are here substituted to match those of Fig. 4.1 for ease) 108 646 P
0.29 (of discussion. As a minor aside, there is an error \050probably typographic?\051 in this manuscript, i.e.,) 72 632 P
-0.57 (L and G are actually reversed. More seriously, E and F are nonexistent, as are the references to pro-) 72 618 P
-0.26 (ducing the lines AF and BE, and the literal translation reads \322Draw forward \050extend\051 lines DA and) 72 604 P
-0.23 (DB until L and G.\323 Here we see the sentence so similar to the one that pervades the 17th, 18th and) 72 590 P
0.65 (19th Century English textbooks that reads \322produce lines DA and DB until L and G.\323 Thus one) 72 576 P
0.56 (possibility is that Adelard of Bath is responsible for introducing the error. However, it is known) 72 562 P
-0.35 (that in the 4th Century Theon of Alexandria\325s recension of the) 72 548 P
1 F
-0.35 (Elements) 370.43 548 P
0 F
-0.35 (, involved altering the lan-) 414.42 548 P
1.98 (guage in some places and sometimes supplying alternative proofs. Furthermore, according to) 72 534 P
-0.69 (Busard [Bu83] all the manuscripts of the) 72 520 P
1 F
-0.69 (Elements) 265.52 520 P
0 F
-0.69 ( known until the 19th Century were derived from) 309.51 520 P
0.18 (Theon\325s text. Therefore it is possible that Theon is the culprit here. On the other hand Adelard of) 72 506 P
0.06 (Bath translated his manuscript from the Al-Hajjaj manuscript in Arabic. Therefore one may won-) 72 492 P
0.81 (der if Al-Hajjaj is to blame. However it is generally considered that the Arabic manuscripts are) 72 478 P
-0.48 (quite trustworthy and other Latin translations of Arabic manuscripts, such as that of Gerard of Cre-) 72 464 P
0.19 (mona have a correct algorithm. Therefore the finger seems to point in the direction of Adelard of) 72 450 P
(Bath.) 72 436 T
2 14 Q
(7.) 72 406.67 T
(The Problems of Language Translation) 108 406.67 T
0 12 Q
0.05 (There are at least two ways in which a correct algorithm may, after some historical evolu-) 108 384 P
0.41 (tion, become an incorrect algorithm. A mathematician such as Theon of Alexandria, in writing a) 72 370 P
0.3 (textbook may offer an alternate algorithm and if he does not understand the deep structure of the) 72 356 P
-0.47 (algorithm may substitute an incorrect one in its place. Another more likely event is that a translator) 72 342 P
0.44 (\050who may not even understand the shallow structure of the algorithm, or who may be totally de-) 72 328 P
-0.44 (pendent on the figure to make sense out of it\051 inadvertently gives an incorrect translated algorithm.) 72 314 P
0.26 (It seems quite probable that a translator such as Adelard of Bath, looking at the figure, may have) 72 300 P
0.85 (thought that a) 72 286 P
1 F
0.85 (ppending AE in a straight line with AD) 139.71 286 P
0 F
0.85 (is a rather clumsy way of stating that) 337.21 286 P
1 F
0.85 (AD) 524 286 P
-0.59 (should be extended) 72 272 P
0 F
-0.59 (, and may have substituted the new phrasing without realizing that an ambiguity) 162.8 272 P
0.31 (has been introduced. The reader may doubt that with such simple and elementary descriptions of) 72 258 P
0.63 (algorithms as are found in Euclid\325s) 72 244 P
1 F
0.63 (Elements) 247.08 244 P
0 F
0.63 ( a translator can become a traitor. An example will) 291.07 244 P
(remove any doubt.) 72 230 T
0.24 (The most accurate and definitive Greek version of the) 108 208 P
1 F
0.24 (Elements) 371.74 208 P
0 F
0.24 (, the Heiberg edition, was) 415.73 208 P
-0.11 (translated in 1978 into French [Ka78]. The book [Ka78] contains, very conveniently, all the prop-) 72 194 P
-0.35 (ositions in both Greek and French side by side. The introduction contains an interesting discussion) 72 180 P
(on the problems of translation which we paraphrase in part.) 72 166 T
1 F
-0.08 (It is no doubt easier to make a literal translation but such an attitude leads to seri-) 108 148 P
0.67 (ous inconveniences for understanding the text. The linguistic differences between) 108 134 P
-0.48 (Greek and French on one side and the evolution of the mathematical vocabulary on) 108 120 P
0.58 (the other are liable to lead the reader into confusion. In the hope of presenting a) 108 106 P
0.82 (directly accessible manuscript we have opted for a free translation remaining as) 108 92 P
-0.69 (true as possible to the text but attaching more importance to the spirit than the letter) 108 78 P
FMENDPAGE
%%EndPage: "17" 7
%%Page: "16" 8
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 16 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
-0.23 (the following \322trick\323 makes the essence \322jump out of the page at you.\323 We fix the construction in-) 72 712 P
-0.48 (stead and for this fixed construction we \322look\323 at all possible input configurations. The crucial part) 72 698 P
-0.28 (of Euclid\325s construction \050missing in Pedoe\325s algorithm [Pe76] and missed by most of Euclid\325s fol-) 72 684 P
0.57 (lowers\051 is the) 72 670 P
1 F
0.57 (cone) 141.36 670 P
0 F
0.57 ( determined by the rays DE and DF and making an angle of 60 degrees at D.) 164.01 670 P
0.29 (This cone is) 72 656 P
1 F
0.29 (implicitly) 133.86 656 P
0 F
0.29 ( constructed by the resulting concatenation of the equilateral triangle DAB) 179.19 656 P
0.35 (and the extensions constructed in) 72 642 P
1 F
0.35 (Step 3) 236.07 642 P
0 F
0.35 (from A to F and B to E. This cone is as large as desired) 269.44 642 P
-0.25 (and always subtends 60 degrees.) 72 628 P
-0.25 (Therefore consider such a cone as fixed in space and refer to Fig.) 230.07 628 P
-0.21 (6.1. Now point A must always lie on one ray DF. Also line segment BC must always have its end-) 72 614 P
-0.43 (point B on the other ray DE. With the compass anchored on B Euclid\325s construction first marks off) 72 600 P
0.69 (a point G on BE such that BG equals BC. Then with the compass anchored on D it marks off a) 72 586 P
0.28 (point L on AF such that DL equals DG. It is clear that for all possible configurations of points A) 72 572 P
-0.47 (and line segments BC the construction is valid. Variation in the distance between A and B does not) 72 558 P
0.43 (change the essence of the proof. Furthermore, all possible relative positions of segment BC with) 72 544 P
-0.31 (respect to point A retain their property of cutting BE at G. It does not matter whether BC is greater) 72 530 P
0.1 (than, less than or equal to AB. Neither does it matter if C lies on AB or DB or for that matter if it) 72 516 P
0.3 (coincides with point A or D! Therefore the algorithm is well defined and executes in all possible) 72 502 P
0.24 (cases. Since in all cases DB equals DA it follows that the algorithm yields the correct solution in) 72 488 P
(all cases as well.) 72 474 T
1.76 (This then is the logic behind Euclid\325s proof and, we might add that, Bertrand Russell) 108 452 P
0.07 ([Ru51] and Dunham [Du90] not withstanding, it holds without the need of a figure. One wonders) 72 438 P
-0.23 (if Russell\325s critique of Euclid is based on the ambiguous and/or incorrect algorithms written down) 72 424 P
3.09 (by 19th century Oxford and Cambridge trained scholars such as [Sm1879], [HS1887] and) 72 410 P
0.65 ([Ta1895] or either on the 12th century Latin manuscript of Gerard of Cremona or Peyrad\325s pre-) 72 396 P
-0.42 (Theonian manuscript, where unambiguous and correct versions of Euclid\325s second proposition ap-) 72 382 P
-0.1 (pear that do not depend on a figure. We see at once Euclid\325s brilliance in the extension of DA and) 72 368 P
-0.03 (DB in the directions of A and B to create the) 72 354 P
1 F
-0.03 (cone) 289.34 354 P
0 F
-0.03 ( with apex at D rather than in the direction of D) 312 354 P
-0.19 (as done by Proclus for example. It is also easy to see with the aid of this) 72 340 P
1 F
-0.19 (cone) 417.46 340 P
0 F
-0.19 ( that indeed there are) 440.11 340 P
0.05 (no proper cases here at all. The cases fabricated and considered by Euclid\325s commentators are ar-) 72 326 P
0.8 (tifacts of a lack of understanding of the underlying logic which, it is conjectured, Euclid had in) 72 312 P
-0.09 (mind when writing this construction and proof. In light of the culturally established belief held by) 72 298 P
-0.25 (so many that Euclid\325s proofs only hold for certain cases together with the fact that almost all mod-) 72 284 P
0.49 (ern versions of the construction are either ambiguous or downright incorrect, it is easy to under-) 72 270 P
-0.62 (stand why Pedoe [Pe76] picks only one such case and claims to give Euclid\325s original proof althou-) 72 256 P
(gh it is missing the crucial construction of the) 72 242 T
1 F
(cone) 294.32 242 T
0 F
( mentioned above.) 316.98 242 T
0.32 (We close this section with a conjecture as to how it came about that so many of the 17th,) 108 220 P
-0.17 (18th and 19th Century English textbooks contain an incorrect algorithm for Euclid\325s second prop-) 72 206 P
0.36 (osition. I believe the answer may lie in the famous Latin translation \050of an Arabic manuscript by) 72 192 P
(Al-Hajjaj\051 due to Adelard of Bath [Bu83].) 72 178 T
1.85 (Amongst the most well known medieval English translators of Euclid\325s) 108 156 P
1 F
1.85 (Elements) 472.5 156 P
0 F
1.85 ( was) 516.49 156 P
-0.39 (Adelard of Bath in the 12th Century. Actually Adelard of Bath\325s name is associated with three dis-) 72 142 P
0.3 (tinct versions of the) 72 128 P
1 F
0.3 (Elements) 171.18 128 P
0 F
0.3 ( and according to Busard [Bu83] it was version II \322that became the) 215.17 128 P
0.16 (most popular of the various translations of the) 72 114 P
1 F
0.16 (Elements) 297.26 114 P
0 F
0.16 ( produced in the 12th Century and appar-) 341.25 114 P
0.24 (ently the one most commonly studied in the schools.\323 Furthermore, this version is apparently the) 72 100 P
-0.35 (least authentic. In the words of Busard [Bu83] \322not only are the enunciations differently expressed) 72 86 P
FMENDPAGE
%%EndPage: "16" 8
%%Page: "15" 9
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 15 -) 293 36 T
72 72 540 486 R
7 X
V
0 X
0.74 (substantial difference in the proof, the practice was to give separate) 108 478 P
1 F
0.74 (enunciations) 442.67 478 P
0 F
(and proofs altogether.\323) 108 464 T
-0.5 (This is indeed the social convention followed even today in computational geometry where) 108 442 P
-0.09 (the phrase \322the remaining cases can be proved in a similar way\323 is seen in almost every published) 72 428 P
(paper in the most scholarly of journals.) 72 414 T
0.29 (It is conjectured though that Euclid saw in) 108 392 P
1 F
0.29 (Proposition 2) 316.27 392 P
0 F
0.29 ( no cases because fundamentally) 382.23 392 P
0.43 (there aren\325t any. Furthermore, if the reader will follow through Euclid\325s original algorithm in all) 72 378 P
-0.37 (the possible \322fabricated\323 cases enumerated in the previous section he or she will find that the algo-) 72 364 P
-0.29 (rithm is well defined in the modern sense and will execute correctly and terminate with the correct) 72 350 P
-0.22 (solution. Furthermore, the proof of correctness also follows through. This cannot be said of any of) 72 336 P
-0.61 (the subsequent algorithms and proofs offered by Heron, Proclus and the other Greek commentators) 72 322 P
-0.1 (of Euclid nor the 19th century English scholars. It should be mentioned here that one logical \050out-) 72 308 P
0.5 (of-context\051 situation consists of) 72 294 P
1 F
0.5 (Case 1.1.1) 228.66 294 P
0 F
0.5 (in which the point A lies at one endpoint of segment) 283.67 294 P
0.08 (BC. Clearly in this pathological situation an equilateral triangle cannot be constructed on AB and) 72 280 P
0.43 (the algorithm would be undefined and fail to execute. However, the context of the situation, i.e.,) 72 266 P
-0.15 (the purpose of the problem is) 72 252 P
1 F
-0.15 (to transfer a distance) 214.43 252 P
0 F
-0.15 (. If A coincides with either B or C then there is) 316.32 252 P
-0.31 (no) 72 238 P
1 F
-0.31 (transfer) 86.69 238 P
0 F
-0.31 ( of distance, the problem does not exist, or if you like, the answer, namely segment BC,) 124.69 238 P
0.14 (is already known at the start. Therefore, the algorithm is clearly intended to work for all points A) 72 224 P
(on the plane except B and C.) 72 210 T
0.57 (The reader may experience an interesting effect upon actually carrying out Euclid\325s con-) 108 188 P
-0.14 (struction and proof for all the cases enumerated above, and that is the) 72 174 P
1 F
-0.14 (Eureka) 406.12 174 P
0 F
-0.14 (experience in which) 443.64 174 P
-0.35 (the) 72 160 P
1 F
-0.35 ( essence, semantics,) 86.66 160 P
0 F
-0.35 (or) 184.58 160 P
1 F
-0.35 ( deep structure) 194.57 160 P
0 F
-0.35 ( behind Euclid\325s construction) 265.86 160 P
-0.35 (is made manifest. Once this) 408.43 160 P
0.43 (happens it is transparently clear that Euclid\325s algorithm and proof of correctness are valid for all) 72 146 P
0.28 (cases one could possibly imagine. In fact in the view expressed here it becomes clear that funda-) 72 132 P
(mentally there are indeed no cases.) 72 118 T
0.48 (It is difficult to grasp the essence of the algorithm-proof by fixing an input configuration) 108 96 P
-0.49 (and then analyzing variations in constructions as in the work of the Greek commentators. However) 72 82 P
297 486 540 730 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
297 486 540 730 R
7 X
0 0 0 1 0 0 0 K
V
333 496 513 522 R
V
0 12 Q
0 X
0.62 (Fig. 6.1 Illustrating the proof of Eu-) 333 514 P
(clid\325s) 333 500 T
1 F
(Proposition 2) 362.66 500 T
0 F
( for all cases.) 428.34 500 T
325.68 543.03 324.24 540.44 2 L
0.5 H
0 Z
N
326.93 542.05 324.24 540.44 324.19 543.57 3 L
N
414 702 325.68 543.03 2 L
2 Z
N
502.32 543.03 503.76 540.44 2 L
0 Z
N
503.81 543.57 503.76 540.44 501.07 542.05 3 L
N
414 702 502.32 543.03 2 L
2 Z
N
417.36 647.16 414.97 647.76 2 L
1 H
0 Z
N
416.6 646.18 414.97 647.76 417.15 648.38 3 L
N
450 639 417.36 647.16 2 L
2 Z
N
417.36 630.84 414.97 630.24 2 L
0 Z
N
417.15 629.62 414.97 630.24 416.6 631.82 3 L
N
450 639 417.36 630.84 2 L
2 Z
N
407.01 578.82 405.58 576.81 2 L
0 Z
N
407.64 577.75 405.58 576.81 405.8 579.07 3 L
N
450 639 407.01 578.82 2 L
2 Z
N
450 615.46 450 613 2 L
0 Z
N
451.13 614.96 450 613 448.87 614.96 3 L
N
450 639 450 615.46 2 L
2 Z
N
501.12 604.92 503.17 603.55 2 L
0 Z
N
502.16 605.59 503.17 603.55 500.91 603.7 3 L
N
450 639 501.12 604.92 2 L
2 Z
N
518.64 656.16 521.03 656.76 2 L
0 Z
N
518.85 657.38 521.03 656.76 519.4 655.18 3 L
N
450 639 518.64 656.16 2 L
2 Z
N
519.7 717.41 521.34 719.25 2 L
0 Z
N
519.18 718.54 521.34 719.25 520.88 717.03 3 L
N
450 639 519.7 717.41 2 L
2 Z
N
0.5 H
270 360 54 54 457 632 A
338 585 356 576 2 L
N
90 450 2 2 379 637 G
1 H
0 Z
90 450 2 2 379 637 A
3 10 Q
(F) 315 532 T
(L) 334 572 T
(A) 366 639 T
(D) 410 707 T
(C) 405 648 T
(C) 405 621 T
(C) 396 566 T
(C) 445 602 T
(C) 526 712 T
(C) 525 654 T
(G) 473 569 T
(C) 507 594 T
(E) 508 533 T
(B) 447 650 T
0 0 612 792 C
72 486 297 720 R
7 X
0 0 0 1 0 0 0 K
V
1 12 Q
0 X
(structure) 72 712 T
0 F
( behind Euclid\325s proof.) 115.33 712 T
2.67 (First we should remember that when) 108 690 P
0.08 (cases did in fact exist Euclid used figures to) 72 676 P
1 F
0.08 (il-) 286.33 676 P
2.28 (lustrate) 72 662 P
0 F
2.28 ( a construction and proof rather than) 108.67 662 P
0.84 (make a) 72 648 P
1 F
0.84 (case) 111 648 P
0 F
0.84 (statement. In the words of Heath) 136.16 648 P
([He28]:) 72 634 T
4.42 (\322To distinguish a number of) 108 616 P
0.06 (cases in this way was foreign to) 108 602 P
7.46 (the really classical manner.) 108 588 P
1.21 (Thus, as we shall see, Euclid\325s) 108 574 P
-0.22 (method is to give one case only,) 108 560 P
4.01 (for choice the most difficult,) 108 546 P
0.41 (leaving the reader to supply the) 108 532 P
3.68 (rest for himself. Where there) 108 518 P
2.09 (was a real distinction between) 108 504 P
0.18 (cases, sufficient to necessitate a) 108 490 P
FMENDPAGE
%%EndPage: "15" 9
%%Page: "14" 10
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 14 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
(between B and C.) 72 712 T
-0.42 (Some of the above cases \050but certainly not all!\051 were discussed by the Greek commentators) 108 690 P
0.41 (and are included in the work of Proclus [Mo70]. Usually a proof that Euclid\325s algorithm worked) 72 676 P
0.03 (correctly was then provided for the particular case at hand. Sometimes the actual) 72 662 P
1 F
0.03 (algorithm) 462.97 662 P
0 F
0.03 (given) 513.34 662 P
-0.46 (by Euclid was changed to handle the special case. For example, for a particular input configuration) 72 648 P
0.63 (in) 72 634 P
1 F
0.63 (Case 2.1) 84.97 634 P
0 F
0.63 ( with the distance between A and B less than the distance between B and C, Proclus) 127.6 634 P
-0.29 (objects to Euclid\325s algorithm because line segment BC \322gets in the way\323 of the construction of tri-) 72 620 P
-0.53 (angle ABD above segment AB \050see Fig. 5.1\051. In the words of Proclus, \322for there is not room.\323 Hea-) 72 606 P
0.13 (th [He28] notes that Heron of Alexandria circa 100 A.D. in his commentary on the) 72 592 P
1 F
0.13 (Elements) 473.55 592 P
0 F
0.13 (also) 520.67 592 P
0.64 (sometimes used constructions different from Euclid\325s to circumvent objections of this type. The) 72 578 P
(algorithm of Proclus [Mo70] for this particular case follows \050see Fig. 5.1\051.) 72 564 T
2 F
(Begin) 108 542 T
1 F
(Step 1) 108 520 T
0 F
(: Let a circle be drawn with center at B and distance BC.) 137.66 520 T
1 F
(Step) 108 498 T
0 F
(2: Let the lines AD and BD be produced to F and G.) 131.66 498 T
1 F
(Step) 108 476 T
0 F
(3: With centre at D and distance DG let the circle GE be described.) 131.66 476 T
([Exit with AE as the solution.]) 108 454 T
2 F
(End) 108 432 T
0 F
-0.22 (Note how Proclus has changed the clear line-extension statements of Euclid\325s algorithm to) 108 410 P
0.5 (the ambiguous statements \050Let the lines AD and BD be produced to F and G.\051 found in the 19th) 72 396 P
(century accounts and that the correctness of the construction is made to depend on the figure!) 72 382 T
-0.52 (Another fascinating manuscript is an Arabic book titled) 108 360 P
1 F
-0.52 (On the Resolution of Doubts in Eu-) 373.79 360 P
0.76 (clid\325s Elements and Interpretation of Its Special Meanings) 72 346 P
0 F
0.76 (written in 1041 A.D. by Ibn al-Hay-) 362.1 346 P
1.06 (tham. A copy of this book made in 1084 A.D. was found in the University of Istanbul Library) 72 332 P
-0.16 ([Ha1041]. As the title suggests this is not a translation of the) 72 318 P
1 F
-0.16 (Elements) 363.79 318 P
0 F
-0.16 ( but a discussion about well) 407.78 318 P
-0.48 (known criticisms of Euclid\325s work. In discussing Euclid\325s second proposition al-Haytham discuss-) 72 304 P
0.04 (es four basic cases in terms of the type of input: \0501\051 point A is either B or C, \0502\051 A lies on the line) 72 290 P
1.04 (segment BC, \0503\051 A lies on the line passing through BC, and \0504\051 A lies outside the line passing) 72 276 P
-0.24 (through BC. In addition to these he has a very strange case that does not appear to have been men-) 72 262 P
0.04 (tioned anywhere else and this is the case when the line segment BC and the point A are separated) 72 248 P
0.24 (by a valley or a river so that the line joining the points A and B cannot be drawn! His solution to) 72 234 P
0.05 (this last case is most puzzling, for he writes that the way to handle this case is to measure the line) 72 220 P
-0.22 (segment and redraw it in the neighborhood of the point, after which Euclid\325s procedure is then ap-) 72 206 P
0.13 (plied! It would appear that Ibn al-Haytham was not lacking a sense of humor in his mathematical) 72 192 P
(writings.) 72 178 T
2 14 Q
(6.) 72 148.67 T
(Euclid\325s Algorithm Reconsidered) 108 148.67 T
0 12 Q
0.5 (It is clear from the above discussion that Euclid\325s followers were concerned that perhaps) 108 126 P
-0.46 (Euclid\325s algorithm and proof of correctness did not hold for all possible configurations of the input) 72 112 P
-0.04 (to the problem. I will argue that the commentators themselves succumbed to the fallacy of \322going) 72 98 P
0.03 (by the figure\323 even more than Euclid himself and that they missed the) 72 84 P
1 F
0.03 (essence) 411.29 84 P
0 F
0.03 (,) 447.94 84 P
1 F
0.03 (semantics) 453.97 84 P
0 F
0.03 (or) 504.32 84 P
1 F
0.03 (deep) 517.34 84 P
FMENDPAGE
%%EndPage: "14" 10
%%Page: "13" 11
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 13 -) 293 36 T
72 72 540 468 R
7 X
V
0 X
0.26 (in fact appears to have been the reaction of early Greek commentators of the) 72 460 P
1 F
0.26 (Elements) 445.5 460 P
0 F
0.26 ( who criti-) 489.49 460 P
0.44 (cized Euclid for leaving out cases that they discovered missing and then supplied accompanying) 72 446 P
-0.5 (proofs of their own. An in depth commentary of Euclid\325s elements and subsequent criticisms made) 72 432 P
-0.44 (against it was written down in the 5th century by Proclus [Mo70]. Proclus himself does not usually) 72 418 P
-0.6 (criticize Euclid and on several occasions actually comes to his defense. In the words of Glenn Mor-) 72 404 P
(row [Mo70]:) 72 390 T
-0.73 (\322When in the proof of a theorem Euclid uses only one of two or more possible cases,) 108 358 P
0.22 (as is his custom, Proclus will often prove one or more of the omitted cases; some-) 108 344 P
0.57 (times he simply calls attention to them and recommends that his readers, \322for the) 108 330 P
1.07 (sake of practice,\323 prove them for themselves. Sometimes he gives an alternative) 108 316 P
0.2 (proof of a theorem devised by one of his predecessors for the obvious purposes of) 108 302 P
(showing the superior elegance or appropriateness of Euclid\325s demonstration.\323) 108 288 T
-0.04 (It is instructive to illustrate some of the objections that early Greek commentators had and) 108 266 P
-0.38 (how they resolved them. First we note that indeed one can conjure up many special cases of an ini-) 72 252 P
-0.28 (tial configuration of point A and line segment BC. For example:) 72 238 P
1 F
-0.28 (Case 1) 380.24 238 P
0 F
-0.28 (: A may lie on the line col-) 412.97 238 P
-0.23 (linear with BC or) 72 224 P
1 F
-0.23 (Case 2) 157.74 224 P
0 F
-0.23 (: A may lie on one side of the line collinear with BC. In) 190.51 224 P
1 F
-0.23 (Case 1) 457.59 224 P
0 F
-0.23 ( A may lie) 490.36 224 P
0.16 (on the line segment BC \050) 72 210 P
1 F
0.16 (Case 1.1) 192.46 210 P
0 F
0.16 (\051 or off the line segment BC \050) 234.62 210 P
1 F
0.16 (Case 1.) 377.39 210 P
0 F
0.16 (2\051. If A lies on BC then in) 413.55 210 P
1 F
-0.05 (Case 1.1.1) 72 196 P
0 F
-0.05 (it may lie on an endpoint of BC or in) 125.91 196 P
1 F
-0.05 (Case 1.1.2) 305.46 196 P
0 F
-0.05 (on the interior of BC, and in the latter) 359.37 196 P
0.57 (case we have two more cases depending on whether A is closer to B or closer to C. In) 72 182 P
1 F
0.57 (Case 1.2) 497.43 182 P
0 F
-0.33 (where A lies off segment BC, A could be closer to B \050) 72 168 P
1 F
-0.33 (Case 1.2.1) 328.33 168 P
0 F
-0.33 (\051 or to C \050) 379 168 P
1 F
-0.33 (Case 1.2.2) 425 168 P
0 F
-0.33 (\051. Furthermo-) 475.67 168 P
-0.07 (re,) 72 154 P
1 F
-0.07 (Case 1.2.1) 87.25 154 P
0 F
-0.07 (divides into two more cases depending on whether the distance between A and B is) 141.1 154 P
-0.38 (greater than or less than the distance between B and C.) 72 140 P
1 F
-0.38 (Case 2) 333.77 140 P
0 F
-0.38 ( in which A lies off the line collinear) 366.39 140 P
0.04 (with BC can also be divided into cases using a variety of criteria. For example we might consider) 72 126 P
-0.04 (two cases depending on whether the line segment BC lies in the interior \050) 72 112 P
1 F
-0.04 (Case 2.1) 423.17 112 P
0 F
-0.04 (\051 or the exterior) 465.13 112 P
-0.68 (\050) 72 98 P
1 F
-0.68 (Case 2.) 76 98 P
0 F
-0.68 (2\051 angle that triangle ABD makes at D. Finally each of these two cases determine two more) 111.32 98 P
-0.09 (cases depending on whether the distance between A and B is greater than or less than the distance) 72 84 P
297 477 540 721 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
297 477 540 721 R
7 X
0 0 0 1 0 0 0 K
V
0.5 H
0 Z
0 X
90 450 81 81 407 634 A
407 634 335 670 2 L
3 H
2 Z
N
3 10 Q
(A) 340 630 T
(B) 412 629 T
(C) 324 673 T
(D) 383 582 T
(G) 349 558 T
(F) 389 543 T
(E) 401 562 T
315 487 522 513 R
7 X
V
0 12 Q
0 X
0.3 (Fig. 5.1 Proclus\325s figure for the proof of a) 315 505 P
(subcase of) 315 491 T
1 F
(Case 2.1 of) 368.32 491 T
(Proposition 2) 425.65 491 T
0 F
(.) 491.33 491 T
353 634 407 634 2 L
0.5 H
N
90 450 2.5 2.5 353.5 633.5 G
0 Z
90 450 2.5 2.5 353.5 633.5 A
354 634 410 524 2 L
2 Z
N
408 635 340 527 2 L
N
0 Z
90 450 27 26.5 379 588.5 A
0 0 612 792 C
72 468 288 720 R
7 X
0 0 0 1 0 0 0 K
V
0 12 Q
0 X
-0.14 (algorithm is designed to work only for inputs) 72 712 P
0.71 (in) 72 698 P
1 F
0.71 (general position) 85.04 698 P
0 F
0.71 (, it should also be able to) 164.09 698 P
-0.52 (handle singularities such as when point A lies) 72 684 P
-0.48 (on the segment BC or A is equidistant from B) 72 670 P
0.05 (and C. Similarly, a proof of correctness must) 72 656 P
1.55 (establish that in all situations the algorithm) 72 642 P
-0.09 (will yield the correct solution. Euclid had the) 72 628 P
0.33 (habit, as is well illustrated by Fig. 4.1, of in-) 72 614 P
0.62 (cluding only one figure to illustrate the con-) 72 600 P
1.29 (struction and proof. It is only natural that a) 72 586 P
0.23 (reader may thus wonder on stepping through) 72 572 P
-0.23 (the algorithm on the given figure whether the) 72 558 P
0.53 (same steps would work on a completely dif-) 72 544 P
1.06 (ferent figure. The same reader may even be) 72 530 P
0.81 (skeptical as to whether the arguments in the) 72 516 P
1.79 (proof of correctness would carry over with) 72 502 P
3.39 (the same letters used as labels of crucial) 72 488 P
1.2 (points derived during the construction. This) 72 474 P
FMENDPAGE
%%EndPage: "13" 11
%%Page: "12" 12
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 12 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
-0.02 (ing Peyrard enough time to finish his translation [Pe1819]. In Peyrard\325s manuscript which he em-) 72 712 P
-0.11 (phasizes is a literal translation, the crucial) 72 698 P
1 F
-0.11 (Step 3) 275.2 698 P
0 F
-0.11 ( is written as \322Menons) 304.76 698 P
1 F
-0.11 ( les droites AE, BZ dans la) 412.31 698 P
(direction de DA, DB,\323) 72 684 T
0 F
( and is thus in agreement with) 180.32 684 T
2 F
(Algorithm Euclid) 327.31 684 T
0 F
( described above.) 416.99 684 T
2 14 Q
(5.) 72 654.67 T
(Cases in Constructions and Proofs) 108 654.67 T
0 12 Q
0.62 (The above discussion brings up naturally the general question of the analysis of) 108 632 P
1 F
0.62 (cases) 501.05 632 P
0 F
0.62 ( in) 527.04 632 P
1.71 (Euclid\325s constructions, modern computational geometry, and geometric proofs in general. We) 72 618 P
0.61 (should note here that when we talk about) 72 604 P
1 F
0.61 (cases) 276.83 604 P
0 F
0.61 ( today we generally mean equivalence classes of) 302.82 604 P
1.57 (input configurations rather than instances of the construction sequence resulting from a set of) 72 590 P
0.07 (choices made as a result of the ambiguities of the algorithm\325s description, as are the case classifi-) 72 576 P
-0.35 (cations in Taylor [Ta1895] and Lardner [La1861]. An algorithm must be specified unambiguously) 72 562 P
1.21 (and should execute correctly for all inputs it was designed to handle. Much criticism has been) 72 548 P
0.25 (heaped on Euclid over the past two thousand years for his alleged sloppiness in his constructions) 72 534 P
-0.19 (and proofs concerning the question of cases. For one thing he has been blamed of giving proofs of) 72 520 P
-0.04 (correctness that depend severely on the figure accompanying the proof. For example according to) 72 506 P
(Bertrand Russell [Ru51]:) 72 492 T
0.98 (\322A valid proof retains its demonstrative force when no figure is drawn, but very) 108 474 P
-0.72 (many of Euclid\325s earlier proofs fail before this test... The value of his work as a mas-) 108 460 P
(terpiece of logic has been very grossly exaggerated.\323) 108 446 T
(Again, in the words of William Dunham [Du90]:) 108 424 T
0.5 (\322Admittedly, when he allowed himself to be led by the diagram and not the logic) 108 406 P
0.19 (behind it, Euclid committed what we might call a sin of omission. Yet nowhere in) 108 392 P
-0.13 (all 465 propositions did he fall into a sin of commission. None of his 465 theorems) 108 378 P
(is false.\323) 108 364 T
(Finally, in the words of Felix Klein [Kl39]:) 108 342 T
0.7 (\322Euclid... always had to consider different cases with the aid of figures. Since he) 108 324 P
-0.52 (placed so little importance upon correct geometric drawing, there is real danger that) 108 310 P
0.65 (a pupil of Euclid may, because of a falsely drawn figure, come to a) 108 296 P
1 F
0.65 (false) 441.69 296 P
0 F
0.65 ( conclu-) 464.36 296 P
(sion.\323) 108 282 T
0.34 (A proposition that has a plethora of cases and that has been the subject of much criticism) 108 260 P
-0.05 (of Euclid is in fact) 72 246 P
1 F
-0.05 (Proposition 2) 163.4 246 P
0 F
-0.05 (, the topic of this paper. It will be argued here using this proposi-) 229.03 246 P
-0.62 (tion as a \322case\323 study that much of the criticism of Euclid regarding case analysis stems from a lack) 72 232 P
-0.09 (of deep understanding of his original work due in part to the writings of the early Greek commen-) 72 218 P
1.05 (tators of the) 72 204 P
1 F
1.05 (Elements) 135.48 204 P
0 F
1.05 ( such as Heron and Theon of Alexandria and others reviewed by Proclus) 179.47 204 P
-0.12 ([Mo70] in the 5th century and exacerbated by a 12th century Latin translation of an Arabic manu-) 72 190 P
0.25 (script by Adelard of Bath [Bu83] and many English scholars of the 19th century. Furthermore, if) 72 176 P
0.38 (we judge the original algorithm and proof of correctness of Euclid\325s) 72 162 P
1 F
0.38 (Proposition 2) 405.84 162 P
0 F
0.38 ( using today\325s) 471.9 162 P
-0.11 (highest standards in the field of computational geometry Euclid deserves praise for his brilliance.) 72 148 P
0.62 (Consider then Euclid\325s second proposition:) 108 126 P
1 F
0.62 (To place at a given point) 321.43 126 P
0 F
0.62 (\050) 447.82 126 P
1 F
0.62 (as an extremity) 451.82 126 P
0 F
0.62 (\051) 526.38 126 P
1 F
0.62 ( a) 530.38 126 P
0.63 (straight line equal to a given straight line.) 72 112 P
0 F
0.63 ( Clearly an algorithm for carrying out this task has to) 279.08 112 P
0.08 (execute, i.e., be well defined for all inputs, i.e., for all possible line segments BC and all points A) 72 98 P
-0.04 (no matter how they are positioned with respect to each other in the plane. Furthermore, unless the) 72 84 P
FMENDPAGE
%%EndPage: "12" 12
%%Page: "11" 13
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 11 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
-0.12 (texts where it is asked to extend DA and DB the phrase \322in) 72 712 P
1 F
-0.12 ( a straight line with) 353.91 712 P
0 F
-0.12 ( DA, DB\323 is absent) 447.47 712 P
-0.04 (because the direction is obviously implied by the extension of the sides of the equilateral triangle.) 72 698 P
0.08 (In) 72 684 P
2 F
0.08 (Algorithm Euclid) 85.07 684 P
0 F
0.08 ( on the other hand extensions emanating from A and B may do so in any di-) 174.82 684 P
-0.68 (rection and thus the phrase \322in) 72 670 P
1 F
-0.68 ( a straight line with) 214.89 670 P
0 F
-0.68 ( DA, DB\323 is provided for precision. The skeptical) 306.17 670 P
-0.45 (reader may nevertheless at first glance insist that the straight line AE may be produced in a straight) 72 656 P
-0.47 (line with DA in such a way that D lies in AE \050in other words, AE emanating from A in the opposite) 72 642 P
-0.05 (direction as that shown in Fig. 4.1\051. However, it is obvious that if this were the case intended, Eu-) 72 628 P
-0.31 (clid would have used the phrase \322Let) 72 614 P
1 F
-0.31 ( the straight line DE be produced in a straight line with AD.\323) 248.08 614 P
0.55 (N) 72 600 P
0 F
0.55 (o room is left here for choosing the direction of the extensions of DA and DB as is clearly the) 80 600 P
(case in) 72 586 T
2 F
(Algorithm 19C) 107.99 586 T
0 F
(.) 184.98 586 T
1.15 (At this point one may wonder about the authenticity and correctness of the accounts of) 108 564 P
-0.68 (Heiberg [He1883], Heath [He28], and Dijksterhuis [Di55]. Here we should point out that the Greek) 72 550 P
-0.64 (text by Heiberg is considered to be the) 72 536 P
1 F
-0.64 (definitive) 254.83 536 P
0 F
-0.64 ( edition. It consists of portions taken from different) 299.5 536 P
-0.51 (Greek manuscripts spanning the 9th to 12th centuries and considered by philologists to be the most) 72 522 P
0.42 (authentic. There also exist several interesting Latin manuscripts which are translations of Arabic) 72 508 P
-0.64 (manuscripts. Perusal of the first printed edition of the Latin translation of the Arabic \050Ishaq-Thabit\051) 72 494 P
-0.08 (version of Euclid\325s) 72 480 P
1 F
-0.08 (Elements) 166.09 480 P
0 F
-0.08 ( believed to be made by the monk Gerard of Cremona in Toledo dur-) 210.08 480 P
-0.18 (ing the 12th century [Bu84] following its discovery in Bagdad, would also appear to be more con-) 72 466 P
0.23 (vincing than examining English texts of the 17th, 18th and 19th centuries. Indeed, apart from the) 72 452 P
-0.33 (fact that the letters E and F in Heath [He28] are absent in [Bu84] and their role subsumed by L and) 72 438 P
0.44 (G, respectively, the algorithms and proofs of correctness found in [He1883], [He28], and [Di55]) 72 424 P
0.44 (are identical to that found in the 12th century Latin manuscript. This 12th century algorithm is a) 72 410 P
-0.26 (Latin translation of an Arabic translation of a Theonian Greek manuscript. In fact all Arabic trans-) 72 396 P
0.6 (lations are believed to descend from the 4th century recension by Theon of Alexandria. Anyone) 72 382 P
1.1 (who has played the translation game may wonder how this version compares with early Greek) 72 368 P
0.05 (manuscripts with respect to the crucial) 72 354 P
1 F
0.05 (Step 3) 260.24 354 P
0 F
0.05 ( which states \050referring to Fig. 4.1\051 \322Let) 289.95 354 P
1 F
0.05 ( the straight) 481.9 354 P
0.24 (lines AE, BF be produced in a straight line with DA, DB.\323 I) 72 340 P
0 F
0.24 (n another 12th century Sicilian Latin) 362.5 340 P
0.84 (translation \050of unknown authorship\051 of Euclid\325s) 72 326 P
1 F
0.84 (Elements) 309.01 326 P
0 F
0.84 ( made) 353 326 P
1 F
0.84 (directly) 386.68 326 P
0 F
0.84 ( from the Greek [Bu87]) 423.34 326 P
1 F
(Step 3) 72 312 T
0 F
( is stated as follows:) 101.66 312 T
(\322Educantur) 108 290 T
1 F
( in directo rectis DA et DB recte AE et BF.\323) 162.65 290 T
0 F
0.65 (This translates to \322Lead) 108 268 P
1 F
0.65 ( forth the straight lines AE and BF in a straight line with \050in the) 224.25 268 P
0.06 (direction of\051 the straight lines DA and DB\323) 72 254 P
0 F
0.06 ( and is thus in agreement with the Gerard of Cremona) 281.43 254 P
(version and Heiberg\325s definitive edition.) 72 240 T
1.16 (As a final piece of evidence that) 108 218 P
2 F
1.16 (Algorithm Euclid) 273.73 218 P
0 F
1.16 ( described above is indeed Euclid\325s) 364.57 218 P
0.05 (original algorithm we consider the so-called manuscript P, the Vatican manuscript No. 190. Until) 72 204 P
-0.33 (1804 all manuscripts of Euclid\325s) 72 190 P
1 F
-0.33 (Elements) 229.35 190 P
0 F
-0.33 ( were believed to be descended from Theon\325s 4th centu-) 273.35 190 P
0.06 (ry recension. When Napoleon conquered Italy he stole from the Vatican a Greek manuscript \050No.) 72 176 P
0.12 (190\051 of Euclid\325s) 72 162 P
1 F
0.12 (Elements) 153.35 162 P
0 F
0.12 ( which he kept in the King\325s Library in Paris. F. Peyrard, a professor at) 197.35 162 P
0.63 (the Lycee Bonaparte, wanted to write a definitive French version of the) 72 148 P
1 F
0.63 (Elements) 425.12 148 P
0 F
0.63 ( using the best) 469.12 148 P
1.32 (Greek manuscripts at his disposal and towards that end obtained access to the King\325s Library.) 72 134 P
0 (There he found manuscript No. 190 and to his astonishment discovered he had in his hands a pre-) 72 120 P
1.29 (Theonian 10th century manuscript. In the mean time the Allied Forces defeated Napoleon and) 72 106 P
0.12 (forced France to return all stolen works of art. On the request of the French government the Pope) 72 92 P
-0.09 (made Peyrard a happy man by granting an extension of the return date of the manuscript thus giv-) 72 78 P
FMENDPAGE
%%EndPage: "11" 13
%%Page: "10" 14
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 10 -) 293 36 T
72 72 540 720 R
7 X
V
0 X
(rithm went up in smoke.) 72 712 T
-0.04 (In spite of the criticism often directed at Euclid, one may find it difficult to believe that he) 108 690 P
-0.14 (could have been guilty of an oversight such as that suggested by Pedoe\325s version of his algorithm.) 72 676 P
-0.09 (On the other hand the consensus of descriptions exemplified by) 72 662 P
2 F
-0.09 (Algorithm 19C) 379.04 662 P
0 F
-0.09 ( given by English) 455.94 662 P
0.37 (scholars such as Lardner [La1861], Todhunter [To1876], Smith [Sm1879], and Hall and Stevens) 72 648 P
-0.6 ([HS1887] as well as) 72 634 P
2 F
-0.6 (Algorithm T) 169.57 634 P
0 F
-0.6 ( of Taylor [Ta1895] and those of the 18th and 17th centuries may) 233.3 634 P
-0.35 (make the reader wonder whether Euclid\325s original algorithm did suffer from similar defects. How-) 72 620 P
0.23 (ever, established authorities on Euclid such as Heiberg [He1883], Heath [He28] and Dijksterhuis) 72 606 P
0.72 ([Di55], have an algorithm significantly different from the ones thus far described. The figure in) 72 592 P
-0.12 (these three works is given in Fig. 4.1. and the algorithm is given below. We omit the proof of cor-) 72 578 P
(rectness as it is exactly the same as that given by Pedoe.) 72 564 T
2 F
(Proposition 2:) 108 542 T
1 F
-0.22 (To place at a given point) 189 542 P
0 F
-0.22 (\050) 310.34 542 P
1 F
-0.22 (as an extremity) 314.33 542 P
0 F
-0.22 (\051) 387.21 542 P
1 F
-0.22 ( a straight line equal to a given) 391.21 542 P
(straight line.) 189 528 T
2 F
(Algorithm) 108 506 T
(Euclid:) 164.33 506 T
0 F
1.51 ([Heath\325s version as well as the original version according the 12th) 207 506 P
(century manuscript of Gerard of Cremona]) 207 492 T
2 F
-0.58 (Input:) 108 470 P
0 F
-0.58 (Let A be the given point, and BC the given straight line. {Thus it is required to place) 143.1 470 P
-0.59 (at the point A \050as an extremity\051 a straight line equal to the given straight line BC.} Fig. 4.1.) 108 456 P
2 F
(Begin) 108 434 T
1 F
(Step 1) 108 412 T
0 F
(: From the point A to the point B let the straight line AB be joined.) 137.66 412 T
1 F
(Step 2) 108 390 T
0 F
(: On AB [using) 137.66 390 T
2 F
(Algorithm 1) 214.33 390 T
0 F
(] let the equilateral triangle DAB be constructed.) 276.66 390 T
1 F
(Step 3) 108 368 T
0 F
(: Let the straight lines AE, BF be produced in a straight line with DA, DB.) 137.66 368 T
1 F
(Step 4) 108 346 T
0 F
(: With centre B and distance BC let the circle CGH be described.) 137.66 346 T
1 F
(Step 5) 108 324 T
0 F
(: With centre D and distance DG let the circle GKL be described.) 137.66 324 T
(Exit with AL as the solution.) 108 302 T
2 F
(End) 108 280 T
0 F
0.34 (Note that in Fig. 4.1 the length of BC is indeed larger than the distance between A and B) 108 258 P
-0.58 (and Pedoe\325s version of Euclid\325s algorithm would not work in this case. However, for a reason mys-) 72 244 P
-0.07 (terious \050I will offer a conjecture later\051 Pedoe leaves out) 72 230 P
1 F
-0.07 ( Step 3) 336.31 230 P
0 F
-0.07 ( in the above version of Euclid\325s al-) 368.84 230 P
0 (gorithm. This crucial step in Euclid\325s algorithm constructs the extensions of DA and DB in direc-) 72 216 P
0.56 (tions E and F, respectively, thus ensuring that whether or not the length of BC is larger than the) 72 202 P
0.32 (distance between A and B, the algorithm continues to \322execute\323 and the figure remains the same) 72 188 P
-0.19 (in the sense that point G exists and lies on BF. Note the significant difference between the manner) 72 174 P
-0.41 (in which DA and DB are to be produced in) 72 160 P
2 F
-0.41 (Algorithm Euclid) 277.21 160 P
0 F
-0.41 ( as compared to) 366.48 160 P
2 F
-0.41 (Algorithm 19C) 443.5 160 P
0 F
-0.41 ( and) 520.08 160 P
2 F
0.93 (Algorithm T) 72 146 P
0 F
0.93 (. In the latter two algorithms the ambiguous instructions state that the) 137.27 146 P
1 F
0.93 (sides of the) 484.13 146 P
0.4 (equilateral triangle) 72 132 P
0 F
0.4 (DA) 169.47 132 P
1 F
0.4 (and) 190.19 132 P
0 F
0.4 (DB) 211.59 132 P
1 F
0.4 (are to be produced.) 231.65 132 P
0 F
0.4 (In) 330.23 132 P
2 F
0.4 (Algorithm Euclid) 343.62 132 P
0 F
0.4 ( on the other hand the) 433.7 132 P
0.86 (statement in Step 3 concerning the extension of DA and DB is unambiguous. It states: \322) 72 118 P
1 F
0.86 (Let the) 506.14 118 P
-0.2 (straight lines) 72 104 P
0 F
-0.2 ( AE, BF) 134.81 104 P
1 F
-0.2 (be produced in a straight line with) 176.87 104 P
0 F
-0.2 ( DA, DB.\323 In other words it specifies that) 341.66 104 P
-0.43 (\0501\051 the extensions are to emanate from A and B \050the endpoints of the base of triangle DAB\051 and \0502\051) 72 90 P
-0.25 (they should be collinear with \050in a straight line with or in the direction of\051 DA and DB. In all other) 72 76 P
FMENDPAGE
%%EndPage: "10" 14
%%Page: "9" 15
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 9 -) 296 36 T
72 207 540 468 R
7 X
V
0 X
(lows us to ignore Lardner\325s caveat intended to resolve it.) 72 460 T
2 14 Q
(4.) 72 430.67 T
(Euclid\325s Construction) 108 430.67 T
(According to Gerard of Cremona and Peyrard) 242.57 430.67 T
0 12 Q
0.34 (One is naturally led to the question: which of all these algorithms is the one Euclid origi-) 108 408 P
0.65 (nally proposed? It would be easy to answer this question by looking up Euclid\325s original manu-) 72 394 P
0.12 (script. Unfortunately history has made this impossible. In the year 332 B.C. Alexander the Great,) 72 380 P
-0.1 (at the age of 24, conquered Egypt and founded the city of Alexandria. When, after conquering the) 72 366 P
-0.65 (rest of the world, he died at the age of 33 in Babylon \050just south of present day Bagdad\051 his generals) 72 352 P
-0.42 (divided up the world into pieces amongst each other. In this way Egypt fell into the hands of Ptole-) 72 338 P
0.57 (my I in 306 B.C. Ptolemy II created the University of Alexandria which became by virtue of its) 72 324 P
0.29 (excellent scholars \050including Euclid\051 and its impressive library \050three quarters of a million books) 72 310 P
0.9 (including Euclid\325s original version of) 72 296 P
1 F
0.9 (The Elements) 259.5 296 P
0 F
0.9 (\051 the intellectual and scientific center of the) 325.4 296 P
0.4 (world. In 48 B.C. Julius Caesar occupied Alexandria and intended to carry a large portion of the) 72 282 P
-0.07 (library with him back to Rome. The academic community held a demostration which was quickly) 72 268 P
-0.07 (quelled by Caesar\325s army. In the ensuing fighting Caesar set fire to the Egyptian fleet in the Great) 72 254 P
0.09 (Harbour. The fire spread to wharehouses on the docks and from there to the library at which time) 72 240 P
-0.45 (many of the books were burned. More books were burned during later Egyptian revolts, one in 272) 72 226 P
0.87 (A.D. quelled by the Emperor Aurelianus and another in 295 A.D. quelled by the Emperor Dio-) 72 212 P
321 486 564 738 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
321 486 564 738 R
7 X
0 0 0 1 0 0 0 K
V
0.5 H
0 Z
0 X
90 450 81 81 447 639 A
90 450 54 54 447 612 A
447 612 447 639 2 L
2 Z
N
447 612 501 612 2 L
3 H
N
447 612 447 531 2 L
0.5 H
N
447 639 348 585 2 L
N
447 612 419 624 2 L
N
3 10 Q
(A) 411 627 T
(B) 450 601 T
(C) 504 609 T
(D) 448 639 T
(G) 452 545 T
(F) 452 525 T
(L) 365 599 T
(E) 337 579 T
(H) 426 671 T
(K) 395 713 T
357 487 537 513 R
7 X
V
0 12 Q
0 X
0.24 (Fig. 4.1 Euclid\325s figure for the proof) 357 505 P
(of) 357 491 T
1 F
(Proposition 2) 370 491 T
0 F
(according to Heath.) 438.67 491 T
90 450 2.5 2.5 419.5 623.5 G
0 Z
90 450 2.5 2.5 419.5 623.5 A
0 0 612 792 C
72 468 315 720 R
7 X
0 0 0 1 0 0 0 K
V
0 12 Q
0 X
-0.66 (tinction \050according to the claim on its front page\051 of) 72 712 P
0.22 (containing the first English translation from Latin.) 72 698 P
1.21 (This appears to contradict the belief that the first) 72 684 P
3.84 (English translation of Euclid\325s) 72 670 P
1 F
3.84 (Elements) 236.67 670 P
0 F
3.84 ( to be) 280.66 670 P
-0.38 (printed was translated by H. Billingsley, printed by) 72 656 P
0.13 (the famous English printer John Day and issued in) 72 642 P
1.05 (1570 [Ar50], [Sh28]. What is worth noting about) 72 628 P
0.38 (the algorithms in all three of these texts, however,) 72 614 P
-0.09 (is that 1\051 they are all identical to each other, 2\051) 72 600 P
1 F
-0.09 ( like) 294.76 600 P
2 F
-0.09 (Algorithm 19C) 72 586 P
0 F
-0.09 (, they are ambiguous but, 3\051) 148.9 586 P
1 F
-0.09 (unlike) 285.67 586 P
0 F
-0.23 (all other algorithms I have encountered, they begin) 72 572 P
0.52 (not by connecting point A to one of the endpoints) 72 558 P
-0.14 (of segment BC but by constructing a circle of radi-) 72 544 P
-0.53 (us BC centered at one of the endpoints of BC. Then) 72 530 P
-0.1 (in the second step point A is joined to the endpoint) 72 516 P
-0.62 (selected as the center in the previous step. Note that) 72 502 P
1.28 (this ordering circumvents the problem that) 72 488 P
2 F
1.28 (Algo-) 287 488 P
-0.36 (rithm T) 72 474 P
0 F
-0.36 ( has with) 111.97 474 P
1 F
-0.36 (Steps 1) 157.21 474 P
0 F
-0.36 (and) 193.82 474 P
1 F
-0.36 (2) 213.79 474 P
0 F
-0.36 ( and furthermore al-) 219.79 474 P
72 72 540 207 R
7 X
V
0 X
0.46 (cletian. In the 4th and 5th centuries the) 72 199 P
1 F
0.46 (polytically-correct-thinking) 265.3 199 P
0 F
0.46 ( movement, with Christianity) 397.95 199 P
-0.63 (as the governmental dogma, became paramount in Alexandria and zealous Christian bishops began) 72 185 P
0.36 (to persecute the pagan writers \050mathematicians\051 and their books. Bishop Theophilus in 391 A.D.) 72 171 P
0.56 (lead a Christian mob and destroyed the Temple of Serapis which housed many of the remaining) 72 157 P
-0.28 (books. The last mathematician alive in Alexandria, a woman by the name of Hypatia and daughter) 72 143 P
0.2 (of Theon was torn limb from limb in the streets of Alexandria by an enraged mob led by Bishop) 72 129 P
-0.37 (Cyril [La41]. Finally, the Arabs invaded Egypt in 646 A.D. and General Amr ibn-al-As burned the) 72 115 P
0.39 (remaining books allegedly because [Be71] \322if the books agreed with the Koran they were super-) 72 101 P
0.53 (fluous; if they disagreed they were pernicious.\323 In short, in all likelihood Euclid\325s original algo-) 72 87 P
FMENDPAGE
%%EndPage: "9" 15
%%Page: "8" 16
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 8 -) 296 36 T
72 72 540 720 R
7 X
V
0 X
1.19 (need not be produced to G. According to the algorithm therefore the solution is given by AG\325) 72 712 P
-0.66 (which is clearly incorrect since AG\325 is smaller than AB whereas BC is greater than AB, by assump-) 72 698 P
0.08 (tion. Therefore although the ambiguities of) 72 684 P
2 F
0.08 (Algorithm 19C) 282.14 684 P
0 F
0.08 (have been removed by Taylor,) 362.3 684 P
2 F
0.08 (Algo-) 512 684 P
0.15 (rithm T) 72 670 P
0 F
0.15 (does not always yield the correct solution on a given) 115.62 670 P
1 F
0.15 (line-point) 372.39 670 P
0 F
0.15 ( configuration depending) 419.06 670 P
0.62 (on which construction strategy is applied. Furthermore,) 72 656 P
2 F
0.62 (Algorithm T) 345.28 656 P
0 F
0.62 ( suffers from an additional) 410.23 656 P
-0.55 (minor bug not even present in) 72 642 P
2 F
-0.55 (Algorithm 19C) 215.38 642 P
0 F
-0.55 (. Notice that) 291.82 642 P
1 F
-0.55 (Step 1) 352.18 642 P
0 F
-0.55 ( in) 381.3 642 P
2 F
-0.55 (Algorithm 19C) 395.54 642 P
0 F
-0.55 ( does not offer) 471.99 642 P
0.06 (choice. However) 72 628 P
2 F
0.06 (Algorithm T) 156.43 628 P
0 F
0.06 ( asks that A be connected to one of the extremities of BC, one that) 220.82 628 P
-0.63 (we are free to choose. However, if we choose to connect A to C \050rather than B as in Taylor\325s figure\051) 72 614 P
(then it is impossible to execute) 72 600 T
1 F
(Step 2) 223.33 600 T
0 F
( and the algorithm crashes.) 253 600 T
1.25 (Another author, Lardner [La1861], also follows his presentation of an ambiguous algo-) 108 578 P
-0.29 (rithm identical to) 72 564 P
2 F
-0.29 (Algorithm T) 156.8 564 P
0 F
-0.29 ( with a discussion of how the student should be careful about diffe-) 220.85 564 P
(rent cases arising from the varieties of different input configurations. In his own words:) 72 550 T
0.8 (\322The different positions which the given right line and the given point may have) 108 532 P
-0.64 (with respect to each other, are apt to occasion such changes in the diagram as to lead) 108 518 P
0.95 (the student into error in the execution of the construction for the solution of this) 108 504 P
(problem.) 108 490 T
0.34 (Hence it is necessary that in solving this problem the student should be guided by) 108 462 P
1.49 (certain) 108 448 P
1 F
1.49 (general) 145.15 448 P
0 F
1.49 (directions, which are independent of any particular arrangement) 186.3 448 P
-0.35 (which the several lines concerned in the solution may assume. If the student is gov-) 108 434 P
-0.24 (erned by the following general directions, no change which the diagram can under-) 108 420 P
(go will mislead him.\323) 108 406 T
-0.37 (Lardner then proceeds to present six general rules concerning what can and cannot be done) 108 370 P
-0.02 (in order to ensure that) 72 356 P
2 F
-0.02 (Algorithm T) 180.23 356 P
0 F
-0.02 ( works correctly on all inputs. This discussion includes a case) 244.54 356 P
0.25 (analysis of construction strategies and, unlike Taylor [Ta1895], does not allow DA and DB to be) 72 342 P
0.56 (extended in either direction but insists that they be extended through the base of the constructed) 72 328 P
-0.19 (triangle thus concluding that the solution to Euclid\325s second proposition has) 72 314 P
1 F
-0.19 (four) 437.59 314 P
0 F
-0.19 ( cases rather than) 457.6 314 P
0.27 (Taylor\325s) 72 300 P
1 F
0.27 (eight) 115.93 300 P
0 F
0.27 (. Another general rule, that Lardner insists should be followed, is that the center of) 139.93 300 P
0.7 (the circle constructed in) 72 286 P
1 F
0.7 (Step 3) 192.79 286 P
0 F
0.7 ( should lie at the extremity of BC connected to A in) 223.16 286 P
1 F
0.7 (Step 1) 482.92 286 P
0 F
0.7 (, thus) 513.29 286 P
(avoiding one of Taylor\325s problems.) 72 272 T
-0.33 (Another variation occurs in a much earlier Scottish book on Euclidean geometry published) 108 250 P
0.51 (in 1831 by John Playfair [Pl1831] which has a variation of) 72 236 P
2 F
0.51 (Algorithm 19C) 361.95 236 P
0 F
0.51 (. In this book we are) 439.45 236 P
0.15 (asked to extend DA and DB to E and F respectively and thus the ambiguity of) 72 222 P
2 F
0.15 (Algorithm 19C) 451.7 222 P
0 F
0.15 ( is) 528.84 222 P
-0.42 (also present here. However, unlike) 72 208 P
2 F
-0.42 (Algorithm 19C) 239.5 208 P
0 F
-0.42 ( or) 316.07 208 P
2 F
-0.42 (Algorithm T) 331.21 208 P
0 F
-0.42 (the algorithm in [Pl1831] first) 397.7 208 P
(performs the extensions and subsequently constructs the circles.) 72 194 T
-0.24 (We close this section with a note on text books of the 18th and 17th centuries. In these two) 108 172 P
-0.55 (centuries combined the number of editions of Euclid\325s) 72 158 P
1 F
-0.55 (Elements) 331.55 158 P
0 F
-0.55 ( published was less than half of the) 375.55 158 P
0.28 (number for the 19th century, about 325 and 280 in the 18th and 17th centuries, respectively. It is) 72 144 P
-0.01 (also much more difficult to find copies of these earlier editions. I have held in my hands only two) 72 130 P
0 (editions from the 18th century [Wi1703], [Ba1705] and one from the 17th century [Cl1654], hav-) 72 116 P
-0.75 (ing found all three in the special collection of the library at Queens University in Kingston, Ontario.) 72 102 P
0.47 (The 1705 manuscript by Issac Barrow \050from Trinity College, Cambridge\051 has the additional dis-) 72 88 P
FMENDPAGE
%%EndPage: "8" 16
%%Page: "7" 17
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 7 -) 296 36 T
72 72 540 720 R
7 X
V
0 X
(the point A a straight line equal BC.} Refer to Fig. 3.2.) 108 712 T
2 F
(Begin) 108 690 T
1 F
(Step 1) 108 668 T
0 F
(:) 137.66 668 T
(Draw AB, the straight line from A to one of the extremities of BC.) 153 668 T
1 F
(Step 2) 108 646 T
0 F
(:) 137.66 646 T
(On it construct an equilateral triangle DAB.) 153 646 T
1 F
(Step 3) 108 624 T
0 F
(:) 137.66 624 T
0.88 (With B as centre and BC as radius, describe the circle CEF, meeting DB \050pro-) 153 624 P
(duced) 153 610 T
2 F
(if) 184.66 610 T
0 F
( necessary\051 at E.) 191.99 610 T
1 F
(Step 4) 108 588 T
0 F
(:) 137.66 588 T
0.6 (With D as centre and DE as radius, describe the circle EGH, meeting DA \050pro-) 153 588 P
(duced) 153 574 T
2 F
(if) 184.66 574 T
0 F
( necessary\051 at G.) 191.99 574 T
(Then AG is the straight line as required.) 108 552 T
2 F
(End) 108 530 T
0 F
-0.44 (Note that Taylor is careful to add in) 108 508 P
1 F
-0.44 (Steps 3) 279.15 508 P
0 F
-0.44 ( and) 313.05 508 P
1 F
-0.44 (4) 335.5 508 P
0 F
-0.44 ( the explicit) 341.5 508 P
4 F
-0.44 (if) 399.86 508 P
1 F
-0.44 ( statements) 407.19 508 P
0 F
-0.44 ( that DB and DA) 460.42 508 P
-0.61 (are to be produced if necessary. Therefore we presume that if the construction circle CEF intersects) 72 494 P
-0.07 (the sides of equilateral triangle ABD then the extension of DA need not be carried out. Unlike the) 72 480 P
0.05 (previous 19th century geometry books Taylor follows the proof of) 72 466 P
1 F
0.05 (Proposition 2) 393.79 466 P
0 F
0.05 (with the follow-) 462.57 466 P
(ing interesting discussion.) 72 452 T
-0.31 (\322It is assumed in this proposition that the straight line DB intersects the circle CEF.) 108 434 P
(It is easily seen that it must intersect in two places.) 108 420 T
0.1 (It will be noticed that in the construction of this proposition there are several steps) 108 392 P
-0.08 (at which a choice of two alternatives is afforded: \0501\051 we can draw either AB or AC) 108 378 P
-0.71 (as the straight line on which to construct an equilateral triangle: \0502\051 we can construct) 108 364 P
0.32 (an equilateral triangle on either side of AB: \0503\051 if DB cut the circle in E and I, we) 108 350 P
0.03 (can choose either DE or DI as the radius of the circle which we describe with D as) 108 336 P
(centre.) 108 322 T
-0.52 (There are therefore three steps in the construction, at each of which there is a choice) 108 294 P
-0.12 (of two alternatives: the total number of solutions of the problem is therefore 2x2x2) 108 280 P
(or eight.\323) 108 266 T
0.34 (We see that Taylor\325s way of dealing with the ambiguities discussed above is to explicitly) 108 230 P
0.82 (acknowledge that there are eight different cases to Euclid\325s proposition that depend on how the) 72 216 P
-0.01 (construction is carried out, that we are free to choose any one of these eight paths through the im-) 72 202 P
0.26 (plied decision-tree, and that the sides DB and DA need not be produced if not necessary. In light) 72 188 P
-0.04 (of this classification let us follow down one path of these choices on the input configuration illus-) 72 174 P
0.45 (trated in Fig. 3.2 where it assumed that the length of CB is greater than the length of CA. In our) 72 160 P
0.36 (first choice we therefore select AB as the segment on which to construct our equilateral triangle.) 72 146 P
0.06 (Our second decision will be to construct the triangle on the side shown in Fig. 3.2. Now since the) 72 132 P
0.3 (circle CEF does not intersect the triangle we extend DB which cuts the circle at the two points E) 72 118 P
0.29 (and I. According to Taylor we may now choose either DE or DI as the radius of the circle which) 72 104 P
0.17 (we describe with D as centre. Accordingly let us choose DI. Now, this circle with D as centre in-) 72 90 P
0.62 (tersects DA at G\325 playing the role of G in his algorithm, and therefore, according to) 72 76 P
1 F
0.62 (Step 4) 485.78 76 P
0 F
0.62 (, DA) 516.06 76 P
FMENDPAGE
%%EndPage: "7" 17
%%Page: "6" 18
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 6 -) 296 36 T
297 477 540 738 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0.5 H
0 Z
0 X
0 0 0 1 0 0 0 K
90 450 99 99 414 630 A
90 450 63 67.5 414 598.5 A
414 612 414 648 2 L
2 Z
N
414 594 360 630 2 L
3 H
N
414 612 414 531 2 L
0.5 H
N
414 648 504 585 2 L
N
414 594 459 612 2 L
N
3 10 Q
(A) 459 600 T
(B) 405 583 T
(C) 347 632 T
(D) 403 644 T
(G) 508 577 T
(H) 487 703 T
324 487 513 513 R
7 X
V
0 12 Q
0 X
-0.28 (Fig. 3.2 Illustrating Taylor\325s version of) 324 505 P
(Euclid\325s) 324 491 T
1 F
(proposition 2.) 367 491 T
3 10 Q
(E) 418 537 T
0 Z
90 450 18 18 414 648 A
(I) 412 671 T
(F) 465 646 T
(G\325) 434 636 T
414 648 414 666 2 L
2 Z
11 X
N
0 X
90 450 2 2 462 613 G
0 Z
90 450 2 2 462 613 A
0 0 612 792 C
72 486 297 720 R
7 X
0 0 0 1 0 0 0 K
V
0 12 Q
0 X
1.42 (the point A a straight line equal BC.}) 108 712 P
(See Fig. 3.1.) 108 698 T
2 F
(Begin) 108 676 T
1 F
(Step 1) 108 654 T
0 F
(: Join AB.) 137.66 654 T
1 F
1.28 (Step 2) 108 632 P
0 F
1.28 (: On AB describe an equilateral) 138.95 632 P
(triangle DAB.) 108 618 T
1 F
0.29 (Step 3) 108 596 P
0 F
0.29 (: From centre B, with radius BC,) 137.95 596 P
(describe the circle CGH.) 108 582 T
1 F
1.15 (Step 4) 108 560 P
0 F
1.15 (: Produce DB to meet the circle) 138.81 560 P
(CGH at G.) 108 546 T
1 F
0 (Step 5) 108 524 P
0 F
0 (: From centre D, with radius DG,) 137.67 524 P
72 72 540 486 R
7 X
V
0 X
(describe the circle GKF.) 108 478 T
1 F
(Step 6) 108 456 T
0 F
(: Produce DA to meet the circle GKF at F.) 137.66 456 T
(Then AF shall be equal to BC.) 108 434 T
2 F
(End) 108 412 T
0 F
0.49 (This algorithm is certainly an improvement over Pedoe\325s algorithm as it appears to work) 108 390 P
0.22 (correctly for some input configurations whether BC is greater than or less than BA. Nevertheless) 72 376 P
-0.17 (the algorithm suffers from ambiguous statements.) 72 362 P
1 F
-0.17 (Step 4) 312.6 362 P
0 F
-0.17 ( asks us to produce \050extend in length\051 DB) 342.09 362 P
-0.23 (to meet the circle CGH at G but it does not tell us in which direction \050emerging from D or from B\051) 72 348 P
-0.37 (to produce DB and certainly in either direction we are bound to meet the corresponding circle con-) 72 334 P
-0.02 (structed in) 72 320 P
1 F
-0.02 (Step 3) 125.3 320 P
0 F
-0.02 (. Fig. 3.1 shows only one possible case but had we produced DB in the direction) 154.94 320 P
0.25 (from B to D instead of the direction shown we would have obtained a completely different inter-) 72 306 P
(section point G. A similar problem exists with) 72 292 T
1 F
(Step 6) 297 292 T
0 F
(.) 326.66 292 T
0.49 (The ambiguities observed in the algorithms described in [Sm1879], and [HS1887] which) 108 270 P
0.03 (are exemplified here as) 72 256 P
2 F
0.03 (Algorithm 19C) 186.73 256 P
0 F
0.03 (are absent in the exposition by Taylor [Ta1895], if not in) 266.77 256 P
-0.4 (the body of the algorithm at least in the subsequent discussion where it is indicated that we are free) 72 242 P
0.47 (to choose one or the other alternative as is) 72 228 P
1 F
0.47 (Step 1.) 281.17 228 P
0 F
0.47 ( It is therefore instructive to examine his algo-) 314.3 228 P
(rithm and accompanying discussion in more detail.) 72 214 T
2 F
(Proposition 2:) 108 170 T
1 F
(From a given point to draw a straight line equal to a given straight line.) 189 170 T
2 F
(Algorithm) 108 148 T
(T:) 164.33 148 T
0 F
( [Taylor\325s version]) 176.33 148 T
2 F
-0.5 (Input:) 108 126 P
0 F
-0.5 (Let A be the given point, and BC the given straight line. {It is required to draw from) 143.17 126 P
FMENDPAGE
%%EndPage: "6" 18
%%Page: "5" 19
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 5 -) 296 36 T
72 72 540 504 R
7 X
V
0 X
-0.66 (of the algorithm makes no sense. Now consider what happens when the length of BC is greater than) 72 496 P
0.12 (the distance from A to B. Clearly the circle centered at B with radius BC will completely enclose) 72 482 P
-0.41 (triangle ABD in its interior and the construction fails! In modern parlance the algorithm is not well) 72 468 P
(defined for such an input and the algorithm crashes.) 72 454 T
2 14 Q
(3.) 72 402.67 T
-0.83 (Euclid\325s Construction) 108 402.67 P
-0.83 (According to 19th, 18th and 17th Century Scholars) 240.91 402.67 P
0 12 Q
-0.64 (During the 19th century \050which witnessed a total of more than 700 editions of) 108 380 P
1 F
-0.64 (The Elements) 475.65 380 P
0 F
-0.29 (published\051 there existed a flurry of activity in England with regards to the writing of text-books on) 72 366 P
0.79 (the topic of Euclid\325s) 72 352 P
1 F
0.79 (Elements) 175.81 352 P
0 F
0.79 ( for use in the schools and colleges. A sample of several of these) 219.8 352 P
0.62 (books [La1861], [To1876], [Sm1879], and [HS1887], yields a common \050apart from some trivial) 72 338 P
-0.32 (notational differences\051 algorithm and illustrative figure for Euclid\325s second proposition. However,) 72 324 P
-0.3 (both the algorithm and figure are quite different from Pedoe\325s [Pe76]. Consider then the algorithm) 72 310 P
(according to one of these sources [HS1887].) 72 296 T
2 F
(Proposition 2:) 108 252 T
1 F
(From a given point to draw a straight line equal to a given straight line.) 189 252 T
2 F
(Algorithm) 108 230 T
(19C:) 164.33 230 T
0 F
( [Popular 19th Century version]) 188.99 230 T
2 F
-0.5 (Input:) 108 208 P
0 F
-0.5 ( Let A be the given point, and BC the given straight line. {It is required to draw from) 140.68 208 P
297 504 540 738 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
297 504 540 738 R
7 X
0 0 0 1 0 0 0 K
V
0.5 H
0 Z
0 X
90 450 81 81 423 639 A
90 450 54 54 423 612 A
423 612 423 639 2 L
2 Z
N
423 612 378 639 2 L
3 H
N
423 612 423 558 2 L
0.5 H
N
423 639 491 597 2 L
N
423 612 446 624 2 L
N
3 10 Q
(A) 451 627 T
(B) 426 601 T
(C) 365 640 T
(D) 417 642 T
(G) 419 546 T
(F) 496 587 T
(H) 402 671 T
(K) 371 713 T
324 511 513 537 R
7 X
V
0 12 Q
0 X
-0.47 (Fig. 3.1 Popular 19th century figure for) 324 529 P
(the proof of Euclid\325s) 324 515 T
1 F
(Proposition 2.) 426.65 515 T
90 450 2 2 446 624 G
0 Z
90 450 2 2 446 624 A
0 0 612 792 C
72 504 297 720 R
7 X
0 0 0 1 0 0 0 K
V
0 12 Q
0 X
(BC. Being what it was required to do.) 108 712 T
2 F
(End of proof.) 108 690 T
0 F
3.01 (We remark here that Pedoe\325s figure,) 108 646 P
3.11 (shown in Fig. 2.2, is considerably different) 72 632 P
0.88 (from those in other sources on Euclid such as) 72 618 P
-0.05 (Heiberg [He1883], Heath [He28] and Dijkster-) 72 604 P
1.28 (huis [Di55] for example. Much more serious,) 72 590 P
-0.16 (however, is the fact that) 72 576 P
2 F
-0.16 (Algorithm P) 189.16 576 P
0 F
-0.16 ( given by) 252.66 576 P
-0.07 (Pedoe is incorrect! It is clear that for a solution) 72 562 P
-0.22 (to be obtained by) 72 548 P
2 F
-0.22 (Algorithm P) 157.11 548 P
0 F
-0.22 ( it is crucial that) 220.55 548 P
-0.62 (the circle centered at B with radius BC intersect) 72 534 P
-0.25 (DB at G. Otherwise G is undefined and the rest) 72 520 P
FMENDPAGE
%%EndPage: "5" 19
%%Page: "4" 20
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 4 -) 296 36 T
72 72 540 522 R
7 X
V
0 X
(equal to the given straight line BC.} Fig. 2.2.) 108 514 T
2 F
(Begin) 108 470 T
1 F
(Step 1) 108 448 T
0 F
(: From the point A to the point B let the straight line AB be joined.) 137.66 448 T
1 F
(Step 2) 108 426 T
0 F
(: On AB [using) 137.66 426 T
2 F
(Algorithm 1) 214.33 426 T
0 F
(] let the equilateral triangle DAB be constructed.) 276.66 426 T
1 F
(Step 3) 108 404 T
0 F
(: With centre B and distance BC let the circle CGH be described.) 137.66 404 T
1 F
(Step 4) 108 382 T
0 F
(: With centre D and distance DG let the circle GKL be described.) 137.66 382 T
(Exit with AL as the solution.) 108 360 T
2 F
(End) 108 338 T
-0.05 (Proof of correctness:) 108 294 P
0 F
-0.05 ( Then, since the point B is the centre of the circle CGH, BC is equal) 214.51 294 P
(to BG.) 108 280 T
0.43 (Again, since the point D is the centre of the circle GKL, DL is equal to DG, and in these) 108 258 P
(DA is equal to DB.) 108 244 T
(Therefore the remainder AL is equal to the remainder BG.) 108 222 T
-0.02 (But BC was also proved equal to BG. Therefore each of the straight lines AL, BC is equal) 108 200 P
(to BG.) 108 186 T
(And things which are equal to the same thing are also equal to one another.) 108 164 T
(Therefore AL is also equal to BC.) 108 142 T
-0.25 (Therefore at the given point A the straight line AL is placed equal to the given straight line) 108 120 P
333 522 540 738 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
333 522 540 738 R
7 X
0 0 0 1 0 0 0 K
V
360 528 531 555 R
V
0 12 Q
0 X
0.17 (Fig. 2.2 Pedoe\325s figure for proving) 360 547 P
(Euclid\325s) 360 533 T
1 F
(Proposition 2) 403 533 T
0 F
(.) 471.67 533 T
0.5 H
0 Z
90 450 36 36 487 612 A
90 450 54 54 423 675 A
486 612 522 612 2 L
3 H
2 Z
N
423 675 486 612 2 L
0.5 H
N
486 612 396 594 2 L
N
396 594 423 675 2 L
N
3 10 Q
(A) 389 580 T
(H) 474 565 T
(B) 482 600 T
(C) 526 609 T
(D) 415 677 T
(L) 395 614 T
(G) 455 646 T
(K) 470 712 T
90 450 2 2 396 594 G
0 Z
90 450 2 2 396 594 A
0 0 612 792 C
72 522 333 720 R
7 X
0 0 0 1 0 0 0 K
V
0 12 Q
0 X
1.96 (science:) 72 712 P
1 F
1.96 (subroutines) 115.61 712 P
0 F
1.96 (. In the algorithm of his second) 171.61 712 P
1 (proposition described next he uses) 72 698 P
2 F
1 (Algorithm 1) 245.34 698 P
0 F
1 (. Be-) 308.67 698 P
0.2 (low we give Pedoe\325s description of Euclid\325s construc-) 72 684 P
(tion.) 72 670 T
2 F
-0.3 (Proposition 2:) 108 626 P
1 F
-0.3 (To place at a given point) 182.74 626 P
0 F
-0.3 (\050) 303.63 626 P
1 F
-0.3 (as an) 307.63 626 P
3.72 (extremity) 108 612 P
0 F
3.72 (\051) 152.65 612 P
1 F
3.72 ( a straight line equal to a given) 156.65 612 P
(straight line.) 108 598 T
2 F
(Algorithm) 108 576 T
(P:) 164.33 576 T
0 F
( [Pedoe\325s version]) 175.66 576 T
2 F
1.37 (Input:) 108 554 P
0 F
1.37 (Let A be the given point, and BC the) 145.05 554 P
-0.22 (given straight line. {Thus it is required to place) 108 540 P
0.74 (at the point A \050as an extremity\051 a straight line) 108 526 P
FMENDPAGE
%%EndPage: "4" 20
%%Page: "3" 21
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 3 -) 296 36 T
72 72 540 549 R
7 X
V
0 X
(straight lines CA, CB be joined.) 108 541 T
2 F
(End) 108 519 T
(Proof of Correctness:) 108 497 T
0 F
(Now, since the point A is the centre of the circle CDB, AC is equal to AB.) 108 475 T
(Again, since the point B is the centre of the circle CAE, BC is equal to BA.) 108 453 T
0.12 (But CA was also proved equal to AB; therefore each of the straight lines CA, CB is equal) 108 431 P
(to AB.) 108 417 T
0.3 (And things which are equal to the same thing are also equal to one another; therefore CA) 108 395 P
(is also equal to CB.) 108 381 T
(Therefore the three straight lines CA, AB, BC are equal to one another.) 108 359 T
0.58 (Therefore the triangle ABC is equilateral; and it has been constructed on the given finite) 108 337 P
(straight line AB. Being what it was required to do.) 108 323 T
2 F
(End of Proof) 108 301 T
0 F
-0.12 (Of course neither Euclid nor Pedoe use the words) 108 257 P
1 F
-0.12 (algorithm, input, begin) 347.91 257 P
0 F
-0.12 (and) 461.24 257 P
1 F
-0.12 (end. N) 481.46 257 P
0 F
-0.12 (either) 512.68 257 P
-0.16 (do they use the phrases) 72 243 P
1 F
-0.16 (proof of correctness) 185.5 243 P
0 F
-0.16 (nor) 284.67 243 P
1 F
-0.16 (end of proof) 303.5 243 P
0 F
-0.16 (, nor do they label separate chunks of) 361.85 243 P
0.06 (the algorithm with the word) 72 229 P
1 F
0.06 (Step) 209.29 229 P
0 F
0.06 (such-and-such. However early Latin manuscripts do preface the) 233.01 229 P
0.76 (construction by the words) 72 215 P
1 F
0.76 (exempli causa) 202.36 215 P
0 F
0.76 ( and the proof by) 271.44 215 P
1 F
0.76 (probatio eius) 360.22 215 P
0 F
0.76 (. We include these well) 424.65 215 P
-0.29 (known terms found in modern computer science for clarity of layout and to delineate that these di-) 72 201 P
0.71 (visions did appear in essence in at least the earliest Arab and Latin translations of Euclid\325s) 72 187 P
1 F
0.71 (Ele-) 520.01 187 P
-0.44 (ments) 72 173 P
0 F
-0.44 (. The important thing is that Euclid always gave the algorithm first and the arguments to sub-) 100 173 P
-0.71 (stantiate the correctness of the algorithm immediately afterwards. Even today too many writers still) 72 159 P
-0.62 (publish geometric algorithms without including a proof of correctness in spite of the many geomet-) 72 145 P
0.67 (ric algorithms that have been found to be incorrect [To84]. These authors could certainly take a) 72 131 P
-0.35 (lesson here from Euclid. Sometimes, as we shall see below, the algorithms in the) 72 117 P
1 F
-0.35 (Elements) 458.03 117 P
0 F
-0.35 ( include) 502.02 117 P
-0.15 (unnecessary steps for obtaining the solution but these steps have the benefit of simplifying the en-) 72 103 P
-0.21 (suing proof of correctness. Euclid also made use of another common practice in modern computer) 72 89 P
72 549 324 720 R
7 X
V
0 X
-0.63 (eral triangle on the straight line AB.} See Fig.) 108 712 P
(2.1.) 108 698 T
2 F
(Begin) 108 676 T
1 F
-0.33 (Step 1) 108 654 P
0 F
-0.33 (: With centre A and distance AB let the) 137.34 654 P
(circle BCD be described.) 108 640 T
1 F
-0.26 (Step 2) 108 618 P
0 F
-0.26 (: With centre B and distance BA let the) 137.41 618 P
(circle ACE be described.) 108 604 T
1 F
-0.22 (Step) 108 582 P
0 F
-0.22 (3: From the point C, in which the circles) 131.44 582 P
2.04 (cut one another, to the points A, B let the) 108 568 P
324 558 540 720 C
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
324 558 540 720 R
7 X
0 0 0 1 0 0 0 K
V
0.5 H
0 Z
0 X
90 450 45 45 408 648 A
90 450 45 45 453 648 A
431 686 408 648 453 648 3 Y
N
3 10 Q
(A) 395 645 T
(B) 457 645 T
(C) 427 694 T
(D) 351 645 T
(E) 502 645 T
360 558 504 585 R
7 X
V
0 12 Q
0 X
2.47 (Fig. 2.1 Euclid\325s figure for) 360 577 P
(the proof of) 360 563 T
1 F
(Proposition 1) 419.65 563 T
0 F
(.) 485.33 563 T
409 648 453 648 2 L
3 H
2 Z
N
0 0 612 792 C
FMENDPAGE
%%EndPage: "3" 21
%%Page: "2" 22
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 2 -) 296 36 T
72 72 540 720 R
7 X
V
0 X
-0.47 (space to some other location to draw a circle with the chosen radius. This operation cannot be done) 72 712 P
0.46 (with a collapsing compass. The collapsing compass is, like the other machines, an) 72 698 P
1 F
0.46 (idealized) 474.55 698 P
0 F
0.46 ( ma-) 517.88 698 P
-0.57 (chine which allows the compass to be opened to a chosen radius and a circle drawn, but no distance) 72 684 P
0.5 (can be) 72 670 P
1 F
0.5 (transferred) 106.99 670 P
0 F
0.5 (. It is as if when the compass is lifted off the work-space it collapses and thus) 160.99 670 P
0.14 (erases any trace of the previous aperture made. Of course more complicated machines can be ob-) 72 656 P
1.98 (tained by combining sets of simple machines. For example in Euclid\325s) 72 642 P
1 F
1.98 (Elements) 434.41 642 P
0 F
1.98 ( he uses the) 478.41 642 P
1 F
-0.29 (straight edge) 72 628 P
0 F
-0.29 ( and) 134.71 628 P
1 F
-0.29 (collapsing compass) 157.46 628 P
0 F
-0.29 ( \050the combination of machines 1 and 3\051 as his model of com-) 251.51 628 P
-0.4 (putation. Attempts have also been made to specify the primitive operations allowed with each type) 72 614 P
-0.56 (of machine [Le02] and to design constructions that require fewer operations than did Euclid\325s orig-) 72 600 P
-0.01 (inal constructions. Another active area of research has been to analyze and compare different ma-) 72 586 P
0.24 (chine models in terms of their computational power [Ho70], [CR81], [Av87], [Av90]. For exam-) 72 572 P
2.72 (ple, in 1672 Georg Mohr [Mo1672] and in 1797 the Italian geometer Lorenzo Mascheroni) 72 558 P
0.15 ([Ma1797] independently proved that any construction that can be carried out with a straight edge) 72 544 P
0.08 (and a compass can be carried out with a compass alone and Jacob Steiner proved in 1833 that the) 72 530 P
-0.4 (straight edge is equivalent in power to the compass if the former is afforded the use of the compass) 72 516 P
0.4 (once [SA48]. To remind the reader that the) 72 502 P
1 F
0.4 (straight edge) 284.83 502 P
0 F
0.4 (and) 351.63 502 P
1 F
0.4 (compass) 372.36 502 P
0 F
0.4 ( are not yet obsolete com-) 413.68 502 P
-0.73 (puters we should point out that the Mohr-Mascheroni result was strengthened as recently as in 1987) 72 488 P
(by Arnon Avron [Av87] at the University of Tel Aviv.) 72 474 T
-0.04 (The earliest proof of the equivalence of models of computation is due to Euclid in his sec-) 108 452 P
0.29 (ond proposition of Book I of the) 72 438 P
1 F
0.29 (Elements) 232.38 438 P
0 F
0.29 ( in which he establishes that the) 276.37 438 P
1 F
0.29 (collapsing) 434.08 438 P
0.29 (compass) 487.37 438 P
0 F
0.29 (is) 532 438 P
-0.39 (equivalent in power to the) 72 424 P
1 F
-0.39 ( compass) 195.76 424 P
0 F
-0.39 (. Therefore in the theory of equivalence of the power of models) 239.7 424 P
0.41 (of computation, Euclid\325s second proposition enjoys a singular place. However, like much of Eu-) 72 410 P
-0.41 (clid\325s work and particularly his constructions involving many cases, his second proposition has re-) 72 396 P
-0.14 (ceived a great deal of criticism over the centuries. In this paper it is argued that it is Euclid\325s com-) 72 382 P
-0.51 (mentators and translators that are at fault and that Euclid\325s original algorithm and proof are beyond) 72 368 P
0.13 (reproach. Since this proposition uses) 72 354 P
1 F
0.13 (Proposition 1) 251.98 354 P
0 F
0.13 ( to obtain a solution we begin by outlining the) 317.79 354 P
(latter.) 72 340 T
2 14 Q
(2.) 72 310.67 T
(Euclid\325s First Two Propositions According to Pedoe) 108 310.67 T
0 12 Q
1.62 (Pedoe [Pe76] contains a lively discussion of Euclid\325s elements of geometry applied to) 108 288 P
0.03 (painting, sculpture and architecture throughout recent history and to illustrate Euclid\325s method he) 72 274 P
-0.05 (presents the first two propositions of Book 1 of his) 72 260 P
1 F
-0.05 (Elements) 318.13 260 P
0 F
-0.05 (. Earlier in the book he actually has a) 362.12 260 P
0.5 (completely different algorithm and proof of) 72 246 P
1 F
0.5 (Proposition 2) 287.65 246 P
0 F
0.5 ( to which we shall return at the end of) 353.83 246 P
0.73 (this paper. However, at this later point in the book he states that \322) 72 232 P
1 F
0.73 (i) 395.84 232 P
0 F
0.73 (t) 399.17 232 P
1 F
0.73 ( is of interest to read how it) 402.51 232 P
0.03 (appears in Euclid.\323) 72 218 P
0 F
0.03 (Subsequently the following algorithms and proofs of correctness are present-) 170.1 218 P
(ed.) 72 204 T
2 F
(Proposition 1:) 108 182 T
1 F
(On a given finite straight line to construct an equilateral triangle.) 183.34 182 T
2 F
(Algorithm) 108 160 T
(1:) 164.33 160 T
-0.13 (Input:) 108 138 P
0 F
-0.13 (Let AB be the given finite straight line. {Thus it is required to construct an equilat-) 143.55 138 P
FMENDPAGE
%%EndPage: "2" 22
%%Page: "1" 23
612 792 0 FMBEGINPAGE
[0 0 0 1 0 0 0]
[ 0 1 1 0 1 0 0]
[ 1 0 1 0 0 1 0]
[ 1 1 0 0 0 0 1]
[ 1 0 0 0 0 1 1]
[ 0 1 0 0 1 0 1]
[ 0 0 1 0 1 1 0]
7 FrameSetSepColors
FrameNoSep
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
0 0 0 1 0 0 0 K
72 744 540 756 R
7 X
0 0 0 1 0 0 0 K
V
72 32 540 44 R
V
0 12 Q
0 X
(- 1 -) 296 36 T
72 72 540 720 R
7 X
V
2 14 Q
0 X
(A NEW LOOK AT EUCLID\325S SECOND PROPOSITION) 120.87 710.67 T
1 12 Q
(Godfried Toussaint) 259.49 688 T
0 F
(School of Computer Science) 237.17 670 T
(McGill University) 261.83 656 T
(Montreal, Quebec) 262.68 642 T
(CANADA) 280.34 628 T
1 F
(Abstract) 285.67 606 T
0 F
-0.38 (There has been considerable interest during the past 2300 years in comparing diffe-) 108 588 P
0.53 (rent models of geometric computation in terms of their computing power. One of) 108 574 P
0 (the most well known results is Mohr\325s proof in 1672 that all constructions that can) 108 560 P
-0.52 (be executed with) 108 546 P
1 F
-0.52 (straight-edge) 190.75 546 P
0 F
-0.52 ( and) 254.74 546 P
1 F
-0.52 (compass) 277.03 546 P
0 F
-0.52 ( can be carried out with) 318.36 546 P
1 F
-0.52 (compass) 431.2 546 P
0 F
-0.52 ( alone.) 472.53 546 P
-0.71 (The earliest such proof of the equivalence of models of computation is due to Euclid) 108 532 P
-0.24 (in his second proposition of Book I of the) 108 518 P
1 F
-0.24 (Elements) 308.81 518 P
0 F
-0.24 ( in which he establishes that the) 352.8 518 P
1 F
-0.41 (collapsing compass) 108 504 P
0 F
-0.41 (is equivalent in power to the) 204.51 504 P
1 F
-0.41 (modern compass) 341.36 504 P
0 F
-0.41 (. Therefore in the) 421.93 504 P
-0.6 (theory of equivalence of models of computation Euclid\325s second proposition enjoys) 108 490 P
1.12 (a singular place. However, like much of Euclid\325s work and particularly his con-) 108 476 P
0.09 (structions involving cases, his second proposition has received a great deal of crit-) 108 462 P
0.27 (icism over the centuries. Here it is argued that it is Euclid\325s early Greek commen-) 108 448 P
0.29 (tators and more recent expositors and translators that are at fault and that Euclid\325s) 108 434 P
0.98 (original algorithm, according to Gerard of Cremona\325s Latin translation of a 12th) 108 420 P
0.1 (century Arabic manuscript as well as Peyrard\325s French translation of a pre-Theon-) 108 406 P
(ian 10th century Greek manuscript, is beyond reproach.) 108 392 T
2 14 Q
(1.) 72 362.67 T
(Introduction) 108 362.67 T
0 12 Q
-0.38 (In the modern comparative study of geometric algorithms it is imperative to first define the) 108 340 P
1 F
1.31 (models of computation) 72 326 P
0 F
1.31 (, i.e., the characteristics of the machine that will execute the algorithms) 183.96 326 P
0.34 ([PS85]. A model of computation specifies the number of) 72 312 P
1 F
0.34 (processors) 350.35 312 P
0 F
0.34 (used, whether they are used) 405.68 312 P
1 F
0.5 (sequentially) 72 298 P
0 F
0.5 (or in) 133.5 298 P
1 F
0.5 (parallel) 159.84 298 P
0 F
0.5 (, the primitive operations allowed and the cost associated with each of) 197.84 298 P
-0.58 (these operations. For example, one of the preferred conceptually abstract models or) 72 284 P
1 F
-0.58 (ideal) 468.26 284 P
0 F
-0.58 ( machines) 492.26 284 P
0.95 (in which many geometric algorithms are compared is the) 72 270 P
1 F
0.95 (Real RAM) 356.89 270 P
0 F
0.95 (\050Random Access Machine) 411.45 270 P
-0.6 ([AHU74]\051 in which each unit of storage space is capable of holding a real number of unlimited pre-) 72 256 P
0.06 (cision and in which the primitive operations that can be performed in one unit of time include the) 72 242 P
-0.22 (arithmetic operations consisting of addition, subtraction, multiplication and division, comparisons) 72 228 P
0.58 (between real numbers, reading from and writing into a storage location as well as perhaps some) 72 214 P
-0.08 (more powerful operations such as computing) 72 200 P
1 F
-0.08 (kth) 290.83 200 P
0 F
-0.08 ( roots, trigonometric functions and other analytic) 305.5 200 P
(functions. More controversial assumptions sometimes include the) 72 186 T
1 F
(ceiling) 389.98 186 T
0 F
(and) 425.64 186 T
1 F
(floor) 445.97 186 T
0 F
( functions.) 469.31 186 T
-0.32 (In classical constructive geometry mathematicians have also been concerned with defining) 108 164 P
1.1 (the) 72 150 P
1 F
1.1 (models of computation) 90.76 150 P
0 F
1.1 (, i.e., the characteristics of the \322machine\323 that will execute the algo-) 202.3 150 P
-0.64 (rithms. Typical machines that have been used in the past starting with Euclid include 1\051 the) 72 136 P
1 F
-0.64 (straight) 502.66 136 P
-0.47 (edge) 72 122 P
0 F
-0.47 (, 2\051 the) 94.66 122 P
1 F
-0.47 (ruler) 129.89 122 P
0 F
-0.47 (, 3\051 the) 153.89 122 P
1 F
-0.47 (collapsing compass) 189.13 122 P
0 F
-0.47 (, 4\051 the) 282.98 122 P
1 F
-0.47 ( compass) 315.7 122 P
0 F
-0.47 (, 5\051 the) 359.55 122 P
1 F
-0.47 (fixed-aperture compass) 394.78 122 P
0 F
-0.47 (, 6\051 the) 507.29 122 P
-0.59 (compass with aperture) 72 108 P
1 F
-0.59 (bounded from above) 181.21 108 P
0 F
-0.59 (, and 7\051 the compass with aperture) 278.68 108 P
1 F
-0.59 (bounded from below) 442.52 108 P
0 F
-0.43 (just to name a few [Sm61], [Ho70], [CR81], [Ko86]. The) 72 94 P
1 F
-0.43 (collapsing compass) 345.65 94 P
0 F
-0.43 ( deserves elaboration) 439.56 94 P
-0.29 (here. With the regular compass one can open it, lock it at a chosen aperture and lift it off the work-) 72 80 P
FMENDPAGE
%%EndPage: "1" 23
%%Trailer
%%BoundingBox: 0 0 612 792
%%PageOrder: Descend
%%Pages: 23
%%DocumentFonts: Times-Roman
%%+ Times-Italic
%%+ Times-Bold
%%+ Helvetica-Bold
%%+ Times-BoldItalic
%%EOF