A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing

Chapter 3

Least-Squares Solutions

Niloy J. Mitra

We start with a simple problem in geometry in the spirit of the

ones discussed in Chapter 1. Given two lines in 2D, find their

point of intersection (see Figure 3.1). Suppose the equations of

the lines are

l

1

: a

1

x + b

1

y + c

1

= 0 ,

l

2

: a

2

x + b

2

y + c

2

= 0 .

(3.1)

(x, y)

l

1

: a

1

x + b

1

y + c

1

= 0

l

2

: a

2

x + b

2

y + c

2

= 0

Figure 3.1: The point of intersection of two lines l

1

and l

2

lies on both

lines and hence satisfies both equations. Given the two lines, we can

solve for their intersection point using a simple linear system (see Equa-

tion (3.3)).

Stating that problem slightly differently, we are looking for a

point (x, y) that ...