Computational Geometry

Course Description

COT4521 – Computational Geometry is a 3-credit-hour upper-division computer science course covering algorithms and data structures for geometric problems. The course addresses computational problems involving points, lines, polygons, and other geometric objects in two and three dimensions — problems that arise across computer graphics, geographic information systems (GIS), robotics, computer-aided design (CAD), computational biology, computer vision, and many other engineering and scientific application areas. Topics include convex hull algorithms; line segment intersection; polygon triangulation; Voronoi diagrams; Delaunay triangulation; range searching; point location; geometric data structures (kd-trees, range trees, segment trees, BSP trees); and the introduction to higher-dimensional and applied geometric algorithms.

Computational geometry occupies a distinctive place in computer science as the intersection of geometric thinking and algorithmic thinking. The field has substantial practical applications across multiple Florida industries (aerospace at the Space Coast, marine engineering, GIS at FDOT, computer graphics at Florida game studios, theme park engineering at Disney/Universal). Coursework typically combines lecture and example-based instruction with substantial programming projects implementing geometric algorithms and analyzing their performance.

COT4521 is a Florida common course offered at approximately 2 Florida institutions. The course transfers as the equivalent course at all Florida public postsecondary institutions per SCNS articulation policy where the receiving program accepts the course. Students should consult their specific program for the appropriate computational geometry course in their degree path; some institutions also offer COT5520 (Computational Geometry at graduate level).

Learning Outcomes

Required Outcomes

Specific outcomes vary across the Florida institutions offering COT4521. Common outcomes typically include:

• Apply computational geometry foundations, including the engineering motivation; the relationship to broader algorithm design; the practical applications across engineering and science.
• Apply geometric primitives and predicates, including the orientation test (predicate for point above/below/on line); the in-circle test; numerical robustness considerations; the engineering implications.
• Apply convex hull algorithms in 2D, including the gift-wrapping algorithm (Jarvis march, O(nh)); Graham scan (O(n log n)); divide-and-conquer convex hull (O(n log n)); the QuickHull algorithm; the analysis of each.
• Apply line segment intersection algorithms, including the brute-force approach (O(n²)); the Bentley-Ottmann algorithm with sweep line approach (O((n + k) log n) where k is the number of intersections); the engineering applications.
• Apply polygon triangulation, including the ear-clipping algorithm; the monotone polygon triangulation; the engineering applications (computer graphics, finite element mesh generation, GIS).
• Apply Voronoi diagrams, including the definition; properties; Fortune's algorithm (sweep line approach, O(n log n)); the engineering applications (nearest-neighbor queries, facility location).
• Apply Delaunay triangulation, including the definition; the duality with Voronoi diagrams; common construction algorithms; the engineering applications (terrain modeling, mesh generation).
• Apply range searching, including 1D range search; 2D range search with kd-trees; range trees with O(log² n) query time; the engineering applications.
• Apply point location, including the planar subdivision point location problem; common approaches (slab method, trapezoidal decomposition with randomized incremental construction); the engineering applications.
• Apply geometric data structures, including kd-trees; range trees; segment trees; interval trees; binary space partitioning trees (BSP trees); the engineering applications.
• Apply numerical robustness considerations, including the challenge of floating-point arithmetic in geometric computations; common robustness techniques (exact arithmetic, predicate evaluation, perturbation); the engineering implications.
• Apply computational geometry to engineering applications, including computer graphics applications, GIS applications, robotics applications, CAD applications.

Optional Outcomes

• Apply 3D computational geometry at introductory level, including 3D convex hulls, 3D Voronoi diagrams, 3D Delaunay triangulation.
• Apply introductory motion planning for robotics applications, including configuration space concepts; visibility graphs; the engineering applications.
• Apply introductory mesh generation, including mesh generation algorithms; quality measures; the engineering applications (finite element analysis preparation).
• Apply introductory geometric optimization, including smallest enclosing circle, smallest enclosing ball; linear programming geometric formulations.
• Apply principles to specific application domains reflecting program emphasis (computer graphics, GIS, robotics, computational biology).

Major Topics

Required Topics

• Computational Geometry Foundations: The role of computational geometry in computer science; the relationship between geometric thinking and algorithmic thinking; the practical applications across engineering and scientific domains.
• Geometric Primitives: Points, lines, line segments, rays; vectors; the standard representations; basic operations.
• Geometric Predicates: The orientation test (CCW — the predicate for point left/right/on a directed line); the in-circle test (whether a point is inside the circumcircle of three other points); the side-of-segment test; numerical robustness considerations; the engineering implications.
• Convex Hull — Definition and Applications: The convex hull as a fundamental geometric structure; the engineering applications (collision detection, shape analysis, statistical analysis).
• Convex Hull — Gift Wrapping (Jarvis March): The algorithm; analysis (O(nh) where n is the number of points and h is the number of hull vertices); the engineering implications (output-sensitive algorithm); when this algorithm is appropriate.
• Convex Hull — Graham Scan: The algorithm (sort by angle, then sweep maintaining a stack); analysis (O(n log n)); the engineering implications.
• Convex Hull — Divide-and-Conquer: The algorithm (recursive division and merging); analysis (O(n log n)); the engineering applications.
• Convex Hull — QuickHull: The algorithm; analysis (expected O(n log n)); the engineering applications and limitations.
• Line Segment Intersection — Brute Force: The brute-force algorithm (check all pairs); analysis (O(n²)); the engineering implications (when this is acceptable).
• Line Segment Intersection — Sweep Line: The Bentley-Ottmann algorithm with sweep line approach; the use of event queue and status data structure; analysis (O((n + k) log n) where k is the number of intersections); the engineering applications (GIS, CAD, graphics).
• Polygon Triangulation — Ear-Clipping: The ear-clipping algorithm; analysis (O(n²) basic, O(n log n) with appropriate data structures); the engineering applications.
• Polygon Triangulation — Monotone Polygons: The decomposition of polygons into monotone pieces; the triangulation of monotone polygons; the engineering applications.
• Voronoi Diagrams: The definition (the partition of the plane into cells based on nearest point); properties (each cell is convex, the diagram has O(n) edges and vertices); the relationship to the perpendicular bisectors of points.
• Fortune's Algorithm for Voronoi Diagrams: The sweep line algorithm; the beach line concept; analysis (O(n log n)); the engineering applications (nearest-neighbor queries, facility location, terrain analysis).
• Delaunay Triangulation: The definition (no point inside the circumcircle of any triangle); the duality with Voronoi diagrams; the maximization of minimum angles property; the engineering applications (terrain modeling, mesh generation, surface reconstruction).
• Delaunay Triangulation Algorithms: The flip algorithm; randomized incremental construction; the analysis of each; the engineering implications.
• Range Searching — Foundations: The range searching problem (find all points in a query region); the engineering applications (database queries, GIS queries).
• Range Searching — 1D Range Search: The 1D range search problem; the use of balanced binary search trees; analysis (O(log n + k) where k is the output size); the engineering implications.
• Range Searching — kd-Trees: The kd-tree data structure; construction; range query algorithm; analysis (O(√n + k) for orthogonal range queries in 2D); the engineering applications.
• Range Searching — Range Trees: The range tree data structure (O(n log n) space, O(log² n + k) query time); the use of fractional cascading; the engineering trade-offs vs. kd-trees.
• Point Location: The planar subdivision point location problem; the slab method (O(log n) query, O(n²) preprocessing); the trapezoidal decomposition with randomized incremental construction; the engineering applications.
• Geometric Data Structures — Segment Trees: The segment tree data structure; common applications (interval queries, range update); the engineering use.
• Geometric Data Structures — Interval Trees: The interval tree data structure; common applications; the engineering use.
• Geometric Data Structures — BSP Trees: Binary space partitioning trees; the construction; common applications (computer graphics, ray tracing); the engineering use.
• Numerical Robustness in Computational Geometry: The challenge of floating-point arithmetic in geometric computations (small errors can produce dramatically wrong topological results); common robustness techniques (exact arithmetic with rational numbers or extended precision; predicate evaluation with controlled error; symbolic perturbation for degenerate cases); the engineering implications.
• Engineering Applications — Computer Graphics: The application of computational geometry to computer graphics (collision detection, hidden surface removal, ray tracing acceleration via BSP trees, mesh processing); Florida applications include the Florida game development industry and theme park engineering.
• Engineering Applications — GIS: The application of computational geometry to geographic information systems (map overlay, spatial queries, terrain analysis); Florida applications include FDOT GIS work, hurricane modeling, environmental analysis.
• Engineering Applications — Robotics: The application of computational geometry to robotics (motion planning, collision detection, configuration space analysis); Florida applications include autonomous vehicle research and aerospace robotics.
• Engineering Applications — CAD: The application of computational geometry to computer-aided design (geometric modeling, mesh generation for finite element analysis); the engineering applications.

Optional Topics

• 3D Computational Geometry: 3D convex hulls (gift wrapping in 3D, divide-and-conquer in 3D); 3D Voronoi diagrams; 3D Delaunay triangulation; the engineering applications.
• Motion Planning: Configuration space concepts; visibility graphs; potential field methods at conceptual level; the engineering applications in robotics.
• Mesh Generation: Mesh generation algorithms (Delaunay-based, advancing front); quality measures; the engineering applications (finite element analysis preparation).
• Geometric Optimization: Smallest enclosing circle (Welzl's algorithm with O(n) expected time); smallest enclosing ball; linear programming geometric formulations; the engineering applications.
• Specific Application Areas: Computer graphics applications at depth; GIS applications at depth; computational biology (structure analysis, alignment); computer vision applications.

Resources & Tools

• Common Texts: Computational Geometry: Algorithms and Applications (de Berg/Cheong/van Kreveld/Overmars — the standard text in computational geometry, often abbreviated dBKOS); Computational Geometry in C (O'Rourke — alternative with C implementations); Discrete and Computational Geometry (Devadoss/O'Rourke); Computational Geometry: An Introduction (Preparata/Shamos — classic foundational text)
• Software Libraries: CGAL (Computational Geometry Algorithms Library — the standard C++ computational geometry library); Shapely (Python library for 2D geometric operations); GEOS (Geometry Engine Open Source, used in PostGIS and many GIS applications); the institutional choice typically depends on program emphasis
• Online Resources: MIT OpenCourseWare 6.838 Geometric Computing; Stanford CS268 Geometric Algorithms; the Computational Geometry course at Utrecht (Marc van Kreveld); the Computational Geometry Pages (compgeom.com)
• Reference Resources: Symposium on Computational Geometry (SoCG — the primary conference); Computational Geometry: Theory and Applications (journal); ACM Transactions on Algorithms; the Computational Geometry Algorithms Library (CGAL) documentation as a reference

Career Pathways

COT4521 supports career pathways requiring computational geometry expertise:

• Computer Graphics Engineering — Direct application; Florida applications include game development studios and theme park engineering at Disney and Universal.
• GIS Engineering — Direct application; Florida applications include FDOT GIS work, environmental analysis, hurricane modeling.
• Robotics Engineering — Computational geometry foundations for motion planning; Florida applications include autonomous vehicle research and aerospace robotics.
• CAD Engineering — Computational geometry foundations for geometric modeling and mesh generation.
• Computer Vision Engineering — Geometric algorithms for image processing and 3D reconstruction.
• Computational Biology — Geometric algorithms for protein structure analysis and other biological applications.
• Game Development — Florida game studios and broader industry; computational geometry for game engines.
• Aerospace Engineering Software — CAD and CAE software development; relevant to Florida aerospace sector (Lockheed, Northrop, L3Harris, Boeing, SpaceX).
• Graduate Computer Science Study — Foundations for graduate study in computational geometry, computer graphics, robotics, computer vision.

Special Information

The Distinctive Place of Computational Geometry

Computational geometry occupies a distinctive place in computer science as the intersection of geometric thinking and algorithmic thinking. Students who succeed in computational geometry typically combine strong algorithmic foundations (from algorithms coursework) with geometric intuition. The field's substantial practical applications across multiple industries make computational geometry skills broadly valuable.

The Numerical Robustness Challenge

Computational geometry is distinctive among algorithm domains for the substantial role of numerical robustness. Geometric algorithms that are correct in exact arithmetic frequently fail in floating-point arithmetic, producing wrong topological results from small numerical errors. The course typically devotes substantial attention to robustness considerations, distinguishing computational geometry from many other algorithm domains.

Florida Industry Applications

Florida hosts substantial computational geometry-relevant industry: aerospace engineering at the Space Coast (CAD, geometric modeling, mesh generation for FEA); marine engineering (geometric modeling for ship and submarine design); GIS at FDOT (transportation network geometry, hurricane evacuation modeling); theme park engineering at Disney and Universal (3D modeling, ride engineering, animation); the Florida game development industry (game engine development, level design tools); Florida computer vision applications (defense, security, agricultural technology).

The Relationship to COT5520

COT5520 is the graduate computational geometry course offered at some Florida institutions. Where COT4521 covers computational geometry at undergraduate level (algorithms, basic data structures, applications), COT5520 extends to graduate level (advanced algorithms, current research, sophisticated data structures). Students should consult their specific program for the appropriate course in their degree path.

General Education and Transfer

COT4521 is a Florida common course number that transfers as the equivalent course at all Florida public postsecondary institutions per SCNS articulation policy.

Course Format

COT4521 is offered in face-to-face, hybrid, and online formats. The combination of mathematical content and programming projects translates to multiple formats; many institutions offer online sections.

Position in the Computer Science Curriculum

COT4521 is typically taken in the senior year of computer science study, often as a specialty elective for students with computer graphics, GIS, robotics, or computational biology interests. The course assumes strong algorithm and programming foundations.

Difficulty and Time Commitment

COT4521 is moderately challenging at the senior level. The course requires substantial out-of-class time (typically 8-10 hours per week beyond class time) for both the mathematical content and the programming projects.

Prerequisites

COT4521 typically requires COT3100C (Discrete Structures) or comparable; COT4400 or COT3400 (Algorithms) or comparable; COP3530C (Data Structures) or comparable; substantial programming experience; senior standing in computer science typical.

AI Integration (Optional)

AI tools can be useful study aids for computational geometry but pose substantive considerations.

Where AI Tools Help

• Concept explanation — alternative explanations of geometric concepts and algorithms
• Algorithm visualization — generating Python code that visualizes geometric algorithms (e.g., convex hull construction, Voronoi diagram construction)
• Implementation drafts — initial implementations as starting point for student understanding (with substantial caution about numerical robustness)
• Test case generation — generating geometric test cases including edge cases and degenerate configurations

Where AI Tools Mislead

• Numerical robustness errors — AI tools frequently generate geometric implementations that fail on degenerate or near-degenerate inputs; students should explicitly test for robustness
• Hallucinated complexity bounds — AI tools sometimes assert complexity bounds that are incorrect
• Surface-level treatment — AI tools may produce explanations that miss the substantive geometric reasoning

Academic Integrity

The use of AI tools to generate algorithm implementations or analyses submitted as student work without permission is academic dishonesty under most institutional policies. Students should consult their institution's specific policies and recognize that the geometric algorithm thinking developed in this course is genuinely valuable for subsequent specialized work in computer graphics, GIS, robotics, and other domains.