O'Reilly logo

Algorithms in a Nutshell, 2nd Edition by Stanley Selkow, Gary Pollice, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 9. Computational Geometry

Computational geometry is the rigorous application of mathematics to compute geometric structures and their properties accurately and efficiently. We confine our discussion to solve problems involving two-dimensional structures represented in the Cartesian plane; there are natural extensions to n-dimensional structures. Mathematicians have investigated such problems for centuries, but the field has been recognized as a systematic study since the 1970s. This chapter presents the computational abstractions used to solve computational geometry problems. These techniques are by no means limited to geometry problems and have many real-world applications.

Algorithms in this category solve numerous real-world problems:

Convex hull

Compute the smallest convex shape that fully encloses a set of n two-dimensional points, P. This can be solved in O(n log n) instead of an O(n4) brute-force solution.

Intersecting line segments

Compute all intersections given a set of n two-dimensional line segments, S. This can be solved in O((n + k) log n) where k is the number of intersections, instead of an O(n2) brute-force solution.

Voronoi diagram

Partition a plane into regions based on distance to a set of n two-dimensional points, P. Each of the n regions consists of the Cartesian points closer to point piP than any other pjP. This can be solved in O(n log n).

Along the way we describe the powerful Line Sweep technique that can be used, ultimately, to ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required