Computational Geometry (Graduate)

Course Description

COT5520 – Computational Geometry is a 3-credit-hour graduate-level computer science course that develops advanced competency in algorithms and data structures for geometric problems. The course extends the undergraduate-level treatment in COT4521 with the depth, theoretical foundations, and research orientation appropriate for graduate computer science students. Topics include rigorous treatment of geometric primitives and predicates with numerical robustness; advanced convex hull algorithms (in 2D and higher dimensions); advanced line segment intersection and geometric arrangement algorithms; advanced Voronoi diagram and Delaunay triangulation algorithms; advanced range searching and geometric data structures; point location with sophisticated data structures; geometric optimization; motion planning foundations; mesh generation; and the engagement with current computational geometry research literature.

Computational geometry 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 advanced geometric algorithms; many institutional implementations include engagement with research literature in computational geometry. Graduate students typically engage substantively with research literature and may develop work suitable for conference submission.

COT5520 is a Florida common course offered at approximately 2 Florida institutions. The course transfers as the equivalent course at Florida public postsecondary institutions per SCNS articulation policy where the receiving graduate program accepts the course; graduate course transfer is typically more restrictive than undergraduate transfer.

Learning Outcomes

Required Outcomes

Upon successful completion of this course, students will be able to:

• Apply geometric primitives and predicates at advanced level, including rigorous treatment of orientation tests, in-circle tests, and other predicates; advanced numerical robustness techniques (exact arithmetic, controlled perturbation, predicate evaluation strategies); the engineering implications.
• Apply advanced convex hull algorithms, including 2D convex hull algorithms at advanced rigor; 3D convex hull algorithms (gift wrapping, divide-and-conquer, randomized incremental construction); higher-dimensional convex hulls at introductory level; lower bounds for convex hull (Ω(n log n) by reduction from sorting).
• Apply line segment intersection at advanced level, including the rigorous treatment of the Bentley-Ottmann algorithm; geometric arrangements and their analysis; the zone theorem; the engineering applications.
• Apply advanced Voronoi diagrams and Delaunay triangulations, including the rigorous treatment of Fortune's algorithm; randomized incremental construction of Delaunay triangulations; weighted Voronoi diagrams (additively weighted, multiplicatively weighted); higher-dimensional Voronoi diagrams at introductory level.
• Apply advanced range searching, including range trees with fractional cascading achieving O(log¹⁻¹ d n + k) query time for d-dimensional orthogonal range queries; partition trees for non-orthogonal range queries; range searching with reporting vs. counting; the engineering implications.
• Apply advanced point location, including the trapezoidal decomposition with randomized incremental construction (O(n log n) preprocessing, O(log n) query); the use of persistent data structures for point location; the engineering implications.
• Apply geometric data structures at advanced level, including kd-trees with advanced analysis; range trees with sophisticated implementations; segment trees and interval trees; binary space partitioning trees with construction and analysis; the engineering applications.
• Apply geometric optimization at intermediate level, including smallest enclosing circle (Welzl's algorithm with O(n) expected time); smallest enclosing ball; geometric linear programming; the engineering applications.
• Apply motion planning foundations, including the configuration space concept; visibility graphs for motion planning among polygonal obstacles; the engineering applications in robotics.
• Apply introductory mesh generation, including Delaunay-based mesh generation; mesh quality measures; the engineering applications (finite element analysis preparation, computer graphics).
• Engage with computational geometry research literature, including the location and rigorous evaluation of peer-reviewed computational geometry research; the conventions of the field; the role of major venues (Symposium on Computational Geometry — SoCG; Computational Geometry: Theory and Applications journal).
• Develop substantive computational geometry projects applying advanced algorithms and data structures to substantial geometric problems, with the depth appropriate for graduate computer science work.

Optional Outcomes

• Apply 3D and higher-dimensional algorithms at advanced level, including 3D Voronoi diagrams and Delaunay triangulations; algorithms for surface reconstruction; the engineering applications in 3D modeling and CAD.
• Apply advanced motion planning, including probabilistic roadmap (PRM) methods; rapidly-exploring random tree (RRT) methods; the engineering applications in robotics and autonomous vehicles.
• Apply geometric approximation algorithms, including ε-nets and ε-approximations at introductory level; coresets at introductory level; the engineering applications.
• Apply introductory geometric optimization at advanced level, including parametric search; the LP-type framework.
• Develop work suitable for conference presentation (SoCG, SODA computational geometry sessions; engineering domain conferences) or peer-reviewed publication.

Major Topics

Required Topics

• Computational Geometry at Graduate Level: The role of computational geometry in modern algorithm research and engineering practice; the relationship to broader algorithm research; the standards for graduate-level computational geometry work.
• Geometric Primitives and Predicates at Advanced Level: The orientation test with rigorous treatment; the in-circle test; predicate evaluation in floating-point arithmetic; exact predicate evaluation techniques; symbolic perturbation for degenerate inputs.
• Numerical Robustness in Computational Geometry: The challenge of floating-point arithmetic in geometric computations; common robustness techniques (exact arithmetic with rational numbers or extended precision; controlled error in predicate evaluation; symbolic perturbation; the use of CGAL's exact predicates); the engineering implications.
• Advanced 2D Convex Hull: The rigorous treatment of Graham scan, gift wrapping, divide-and-conquer, and QuickHull; lower bounds for convex hull (Ω(n log n) by reduction from sorting); output-sensitive algorithms (Chan's algorithm with O(n log h)).
• 3D Convex Hull: Gift wrapping in 3D; divide-and-conquer in 3D; randomized incremental construction of 3D convex hulls; the analysis of each.
• Higher-Dimensional Convex Hull: The combinatorial complexity of convex hulls in high dimensions; algorithms for high-dimensional convex hulls at introductory level; the engineering implications.
• Line Segment Intersection — Advanced: Rigorous treatment of the Bentley-Ottmann algorithm; the analysis with floating-point robustness considerations; engineering applications (GIS overlay, CAD boolean operations).
• Geometric Arrangements: Arrangements of lines, line segments, and curves; the combinatorial complexity (the zone theorem); algorithms for constructing arrangements; the engineering applications.
• Voronoi Diagrams — Advanced: Rigorous treatment of Fortune's algorithm; weighted Voronoi diagrams (additively weighted, multiplicatively weighted); Voronoi diagrams of line segments; higher-order Voronoi diagrams (k-th nearest neighbor).
• Delaunay Triangulation — Advanced: Randomized incremental construction with rigorous analysis (O(n log n) expected); the lifting to higher dimensions (Delaunay triangulation as the lower hull of points lifted to a paraboloid); constrained Delaunay triangulation; the engineering applications.
• Range Searching — Range Trees with Fractional Cascading: The standard range tree (O(n logⁿ n) space, O(log¹⁻¹ d n + k) query); the use of fractional cascading to improve query time to O(log¹⁻¹ d n + k); the engineering trade-offs.
• Range Searching — Partition Trees: The general partition tree framework for non-orthogonal range queries; the analysis; the engineering applications.
• Point Location — Advanced: Trapezoidal decomposition with randomized incremental construction (O(n log n) preprocessing, O(log n) query, O(n) space); the analysis; the use of persistent data structures for point location; the engineering applications.
• Advanced Geometric Data Structures: kd-trees with rigorous analysis; quad-trees and oct-trees; R-trees for spatial indexing; the engineering applications in databases and GIS.
• Geometric Optimization: Smallest enclosing circle (Welzl's algorithm with O(n) expected time); smallest enclosing ball in higher dimensions; the LP-type framework for geometric optimization; geometric linear programming with parametric search; the engineering applications.
• Motion Planning Foundations: The configuration space concept; visibility graphs for motion planning among polygonal obstacles; the analysis of motion planning algorithms; the engineering applications in robotics.
• Mesh Generation — Introduction: Delaunay-based mesh generation; advancing front methods; mesh quality measures; the engineering applications (finite element analysis preparation, computer graphics).
• Computational Geometry Research Engagement: The location and evaluation of peer-reviewed computational geometry research; the role of the Symposium on Computational Geometry (SoCG — the primary conference); the journals (Computational Geometry: Theory and Applications; Discrete & Computational Geometry); current research directions.
• Computational Geometry Project: Substantive project applying advanced algorithms and data structures to a substantial geometric problem, with the depth appropriate for graduate computer science work.

Optional Topics

• 3D and Higher-Dimensional Algorithms: 3D Voronoi diagrams and Delaunay triangulations; algorithms for surface reconstruction (alpha shapes, ball pivoting); the engineering applications in 3D modeling, CAD, computer graphics, and computational biology.
• Advanced Motion Planning: Probabilistic roadmap (PRM) methods; rapidly-exploring random tree (RRT) methods; the analysis at conceptual level; the engineering applications in robotics and autonomous vehicles.
• Geometric Approximation Algorithms: ε-nets and ε-approximations at introductory level; coresets for geometric problems; approximation for geometric optimization problems.
• LP-Type Problems: The LP-type framework as a generalization of linear programming; the analysis of algorithms for LP-type problems; the engineering applications.
• Specific Application Areas: Computer graphics applications at advanced level; GIS applications at advanced level; computational biology (structure analysis, alignment); robotics 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); Discrete and Computational Geometry (Devadoss/O'Rourke); Handbook of Discrete and Computational Geometry (Goodman/O'Rourke/Tóth — graduate research reference)
• Software Libraries: CGAL (Computational Geometry Algorithms Library — the standard C++ computational geometry library, with substantial graduate-level use); Shapely (Python library); GEOS (used in PostGIS); the institutional choice typically depends on program emphasis
• Research Resources: Symposium on Computational Geometry (SoCG — the primary conference); ACM-SIAM Symposium on Discrete Algorithms (SODA — frequently has computational geometry papers); Computational Geometry: Theory and Applications (the primary journal); Discrete & Computational Geometry (broader scope)
• Online Resources: The Computational Geometry Pages (compgeom.com); the Computational Geometry course materials at major research universities (Stanford, Utrecht, MIT, Tel Aviv)

Career Pathways

COT5520 supports advanced career pathways in computational geometry-relevant industries:

• Computer Graphics Engineering — Senior — Senior software engineering and research at major graphics companies (Pixar, NVIDIA, AMD, Apple, Disney, others); Florida applications include theme park engineering at Disney and Universal.
• GIS Engineering — Senior — Senior GIS engineering roles; Florida applications include FDOT GIS work, environmental analysis, hurricane modeling.
• Robotics Engineering — Senior — Senior robotics engineering work requiring sophisticated geometric algorithms; Florida applications include autonomous vehicle research (CAV testbeds at SunTrax, Tampa, Babcock Ranch) and aerospace robotics.
• CAD and CAE Engineering — Senior — Senior software engineering at CAD vendors (Autodesk, Dassault Systèmes, Siemens, Ansys, others); engineering applications across Florida's aerospace and engineering sectors.
• Computer Vision Research and Engineering — Senior computer vision work requiring advanced geometric algorithms.
• Computational Biology Research — Senior research in protein structure analysis, computational genomics, computational drug design.
• Game Engine Engineering — Senior — Senior game engine development at major game companies and Florida studios.
• Doctoral Computer Science Study — Strong preparation for PhD work in computational geometry, computer graphics, robotics, computer vision.
• Faculty Career Path — University faculty positions in computational geometry, computer graphics, or related areas.

Special Information

Graduate-Level Treatment

COT5520 differs from undergraduate COT4521 in several substantive ways: theoretical depth (graduate students engage with the rigorous proofs of algorithm correctness and complexity); methods sophistication (advanced topics such as range trees with fractional cascading, randomized incremental construction, parametric search, LP-type problems); research orientation (engagement with peer-reviewed computational geometry research); and project sophistication (substantial geometric algorithm work appropriate for graduate study).

The CGAL Library

The Computational Geometry Algorithms Library (CGAL) is the standard C++ library for computational geometry and is widely used in both research and industry. CGAL provides robust implementations of essentially all the major computational geometry algorithms with proper handling of numerical robustness. Graduate students working with computational geometry typically engage substantively with CGAL.

The Numerical Robustness Challenge — Graduate Treatment

Graduate-level computational geometry treats numerical robustness with substantial rigor. The course typically covers exact predicate evaluation strategies, controlled-precision arithmetic, symbolic perturbation for degenerate inputs, and the practical use of CGAL's robust geometric kernel. The depth of treatment distinguishes graduate from undergraduate computational geometry.

Research Engagement

Computational geometry operates as a substantive research community with its own primary conference (SoCG) and journals. COT5520 connects students to this community through engagement with research papers, attention to research conventions, and (in many institutional implementations) the development of research artifacts.

General Education and Transfer

COT5520 is a Florida common course number that transfers as the equivalent course at Florida public postsecondary institutions per SCNS articulation policy where the receiving graduate program accepts the course. Graduate course transfer is more restrictive than undergraduate transfer.

Course Format

COT5520 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 to support working professional students.

Position in the Graduate Computer Science Curriculum

COT5520 is typically taken as a specialty graduate course in computer graphics, robotics, GIS, or related tracks. The course is well-positioned for thesis or dissertation research in computational geometry-related areas.

Difficulty and Time Commitment

COT5520 is moderately challenging at the graduate level. The course requires substantial out-of-class time (typically 9-12 hours per week beyond class time) for both the mathematical content and the programming projects.

Prerequisites

COT5520 typically requires bachelor's degree in computer science or related discipline; admission to a graduate computer science program; proficiency in undergraduate algorithms (COT4400, COT3400, or comparable); strong mathematical maturity; foundational programming proficiency in C++ or Python.

AI Integration (Optional)

AI tools can serve as study aids in graduate computational geometry but pose substantive considerations.

Where AI Tools Help

• Concept exploration — alternative explanations of advanced geometric concepts
• Algorithm visualization — generating Python code that visualizes geometric algorithms
• Implementation drafts — initial implementations as starting points (with substantial caution about numerical robustness, which AI tools frequently get wrong)
• Literature engagement — helping summarize research papers (with rigorous verification)

Where AI Tools Mislead at Graduate Level

• Numerical robustness errors — AI tools frequently generate geometric implementations that fail on degenerate or near-degenerate inputs; graduate-level robustness expectations are higher than typical AI output
• Hallucinated research results — AI tools sometimes assert computational geometry results that don't exist in the literature
• Surface-level treatment — AI tools may produce explanations that miss the substantive geometric and algorithmic reasoning
• Hallucinated complexity bounds — AI tools sometimes assert complexity bounds that are incorrect

Academic Integrity at Graduate Level

Graduate-level academic integrity expectations are stricter than undergraduate. The use of AI tools to generate algorithm implementations or analyses submitted as student work is academic dishonesty under most institutional policies. Graduate students should consult their institution's specific policies and recognize that the geometric algorithm thinking developed at the graduate level is foundational for research careers and senior industry roles — bypassing its development through AI tools fundamentally compromises preparation for those careers.