Working With Dingshu Du's Approach to Euclidean Geometry Computation
I've spent more years than I'd like to admit wrestling with coordinate-based geometry proofs and computational geometry problems, and Dingshu Du's work on Computing In Euclidean Geometry is one of those references that shows up on my desk repeatedly. It's not a textbook you read cover to cover. It's a manual you consult when your brute-force coordinate method breaks down or when you need a cleaner algorithmic path. The book covers a broad range of computational techniques applied to classical Euclidean geometry. The core value is in the algorithmic treatment of constructions, distance calculations, intersection problems, and geometric transforms. Du organizes things by problem type rather than by mathematical theory, which is why it's useful as a working reference.
Computing In Euclidean Geometry Dingshu Du
If you're coming in cold, the way this book actually functions in practice is quite different from how a traditional geometry text works. You pick a problem category, look at the algorithmic framework Du lays out, and then adapt it. For example, the section on determining whether four points are concyclic is presented as a sequence of predicate checks with explicit numerical tolerances baked in. That's the part most people skip over when they're rushing through it, but those tolerances matter when you move from pure math into floating-point implementation. I ran into a concrete issue a while back while implementing a polygon clipping routine that Du references in the intersection chapter. The algorithm assumes exact arithmetic when computing line-segment intersections, which is fine on paper. In practice, with double-precision floats, I kept getting inconsistent results on collinear edge cases. The workaround wasn't to change the math but to add a collinearity check before dropping into the general intersection formula. Specifically, I computed the cross product magnitude and compared it against an epsilon scaled by the segment lengths rather than using a fixed epsilon. That small change eliminated the race conditions I was seeing on degenerate inputs. The book also handles circle constructions and tangents in a way that's unusually practical for someone writing production geometry code. Du doesn't just state the formulas. He works through the numerical stability concerns, which is rare. Most sources will give you the standard algebraic derivation and leave you to figure out why your implementation diverges on nearly-tangent circles. Du points out that the standard quadratic formula approach becomes unstable when the discriminant is very small relative to the leading coefficients, and he offers an alternative formulation that avoids that pitfall.
One thing that catches people off guard is how much of the book relies on homogeneous coordinates and projective extensions, even though the title promises Euclidean geometry. This is intentional. Many Euclidean problems become simpler when lifted into projective space, solved there, and then mapped back. If you're not comfortable with that framework, the transition sections will feel abrupt. I'd recommend brushing up on homogeneous coordinates before diving in, or at least keeping a reference like Coxeter's projective geometry text nearby.
Get the Full Details
How to Get the Most Out of This Material
Start with the chapters that match your immediate problem set. The book is structured so you can jump in without reading everything sequentially. If you're working on collision detection or mesh processing, the distance and intersection chapters will be relevant first. If you're doing CAD-related work, the construction and transformation sections will come in handy sooner. The code examples, where they exist, are mostly pseudocode or MATLAB-style snippets. You'll need to translate them. That translation step is where the real learning happens, and where most people hit snags. A specific pain point I noticed repeatedly is the treatment of circular arc parameters. Du's arc definitions use angle ranges that assume a particular orientation convention, and if your coordinate system has a flipped Y axis, your arc traversal order reverses without any warning. I learned this the hard way when a sweep-line implementation produced visibly wrong output on a test dataset that looked identical to the examples. Another limitation worth noting upfront is that the book doesn't cover computational geometry in higher dimensions. Everything is two or three dimensional at most. If you need something beyond that, you'll need to extend the methods yourself or look elsewhere. There's also no coverage of randomized algorithms or Monte Carlo approaches to geometric problems, which means if your application involves stochastic geometry or probabilistic shape analysis, this reference won't help you there.
The material on geometric optimization, particularly the chapters on shortest path and Voronoi-related constructions, is solid but assumes a certain baseline familiarity with graph algorithms. If you're not comfortable with Dijkstra variants or planar subdivision techniques, those sections will move fast. I'd suggest building that foundation separately before attempting to implement those parts.
Practical Implementation Notes
When you actually sit down to implement anything from this book, precision handling is the first thing you need to decide on. Du's algorithms assume exact arithmetic in the theoretical descriptions, but every real implementation deals with finite precision. I tend to use a two-tier approach: exact rational arithmetic for the predicate decisions and floating point for the coordinate computations. The Shewchuk predicates library handles the orientation and incircle tests reliably, and once you've established the combinatorial structure exactly, the floating-point coordinates can be used for metric calculations without back-propagating topological errors. There's also a section on geometric predicates that many readers gloss over because it reads more like a catalog than a tutorial. Don't skip it. The predicate choices you make early in a geometry pipeline determine whether your code is going to be fragile or robust later on. Picking the wrong predicate for a given configuration is one of the most common sources of subtle bugs in computational geometry, and Du's systematic treatment of when each predicate applies is genuinely useful if you pay attention to it. If you're looking to access the book, it's available through standard academic channels and major online retailers. The ISBNs vary by edition, so checking the publisher's listing for the version you want is the safest route. There are no official digital versions distributed directly by the publisher, though scanned copies circulate on academic file-sharing platforms. I don't endorse piracy, but the book is expensive and out of print in some formats, which is a practical barrier worth acknowledging.
The real utility of this material comes from working through the examples yourself and stress-testing them against degenerate cases. Du gives you the frameworks. The implementation details, the tolerance choices, the edge-case handling, that's where the actual work is. Anyone who tells you otherwise is either selling something or hasn't tried to productionize these algorithms yet.
