Adis Alihodžić | Exploring Computational Geometry. Theory and Python Implementations (2026) [PDF] [EN]

Topics and features:

· All geometric algorithms implemented in native Python

· 400+ illustrations and visualizations

· Includes project-based exercises for students

· Coverage: Core Structures and Algorithms, Geometric Objects in Python, Algorithms for Geometric Objects, Convex Hull Algorithms in 2D and 3D, Polygon Triangulation Methods, Delaunay Triangulation, Voronoi Diagrams, Visualization Techniques, Algorithms for Space Exploration, Quadtrees, Robot Motion Planning, AI in Computational Geometry

· Suitable for advanced undergraduate and graduate courses

· GitHub repository with all source code

Ideal for students of computer science, the textbook/reference will have real utility as well for those in mathematics and engineering. Researchers and practitioners working in computational geometry, algorithm design, data visualization, or related disciplines will find the work an indispensable resource and guide.

Adis Alihodžić is a Full Professor at the Department of Mathematics and Computer Science, Faculty of Natural Sciences and Mathematics, University of Sarajevo.

Contents Preface xi
ListofSymbols........................................................ xvii
ListofAlgorithms...................................................... xxi
ListofImplementations.............................................. xxiii
ListofFigures............................................xxv
ListofTables........................................................xxxiii
AbouttheAuthor....................................................xxxv
1CoreStructuresandAlgorithms.......................................1
1.1ObjectBehaviorandProgramStructureinPython11.1.1
CreatingObjects...........................................................21.1.2
InvokingMethodsonObjects.................................................21.1.3
OverloadingofOperators....................................................31.1.4
ProgramStructure:Modules,Indentation,MainFunction.........................41.1.5
DesignPatternsandPracticalExtensionsinPython...............................4
1.2ComputationalComplexity51.2.1
ComputerArchitectureandMemoryAccess...................................51.2.2
AccessingElementsinPythonLists.............................................61.2.3
TimeComplexityNotation....................................................61.2.4
AsymptoticAnalysisandNotation.............................................7
1.3RecursiveFunctionCallsandScopesinPython81.3.1
ScopesandMemoryManagement...........................................91.3.2
TheRoleoftheStackandHeapinRecursiveAlgorithms.........................101.3.3
UnderstandingRecursiveCallStacks..........................................11
1.4OrderedCollections131.4.1
ListsandTheirOperations...................................................131.4.2
AlgorithmsforSortingCollections.............................................161.4.3
LinkedListsandTwo-DimensionalArrays.......................................171.4.4
StacksandQueues........................................................19
1.5HashTables,Sets,Maps,andtheRoleofMemoization201.5.1
HashTables...............................................................211.5.2
Sets......................................................................211.5.3
Maps.....................................................................221.5.4
Memoization..............................................................23
1.6Trees231.6.1BinarySearchTrees.........................................................251.6.2
BalancedBinarySearchTrees................................................261.6.3
AVLTrees.................................................................27
2GeometricObjectsinPython........................................31
2.1VectorsinthePlane31
2.2PointsinthePlane33
2.3LineSegmentsinthePlane372.3.1Segment-SegmentIntersectionTest...........................................40
2.4VerticesandTheirRoleinGeometricStructures43
2.5Polygons:StructureandRepresentation432.5.1ExamplesofUsingthePolygonClass..........................................51
2.6Triangles:BasicBuildingBlocksofGeometry52
2.7PointsinThree-DimensionalSpace52
2.8TrianglesasFundamentalUnitsin3DGeometry54
2.9LineSegmentsin3D61
2.10Exercises67
3AlgorithmsforGeometricObjects...................................69
3.1IntersectionofSegments693.1.1
VisualizationofGeometricAlgorithmsinPython................................703.1.2
ExhaustiveSearchApproach................................................713.1.3
EfficientMethod...........................................................73
3.2ClippingaSegmentwithaRectangle80
3.3ClippingaConvexPolygonandaSegment85
3.4ClippingofaRectangleandaConcavePolygon89
3.5IntersectionofConvexPolygons91
3.6IntersectionofHalf-Planes98
3.7UnionofRectangles100
3.8Exercises110
4ConvexHullAlgorithms..............................................111
4.1AlgorithmsintheTwo-DimensionalCase112
4.1.1SimplePolygon...........................................................1124.1.2
ConvexHull..............................................................1144.1.3
GiftWrapping............................................................1184.1.4
GrahamScanAlgorithm...................................................1194.1.5
Andrew’sAlgorithm.......................................................1254.1.6
IncrementalAlgorithm.....................................................1274.1.7
QuickHullAlgorithm.......................................................1314.1.8
MergehullAlgorithm.......................................................1334.1.9
Chan’sAlgorithm.........................................................1364.1.10
Akl–ToussaintHeuristic.....................................................1384.1.11
PerformanceEvaluationofConvexHullAlgorithms............................139
4.2AlgorithmsintheThree-DimensionalCase140
4.2.1PlatonicSolids............................................................1444.2.2
NaiveAlgorithmfor3DConvexHullConstruction..............................1454.2.3
Jarvis’sAlgorithmfor3DConvexHullConstruction.............................1504.2.4
IncrementalAlgorithmfor3DConvexHullConstruction.........................1514.2.5
RecursiveAlgorithmfor3DConvexHullConstruction...........................153
4.3Exercises154
5PolygonTriangulationMethods.....................................157
5.1PropertiesofSimplePolygons157
5.2AlgorithmsforTriangulatingaSimplePolygon164
5.2.1NaiveAlgorithm..........................................................1645.2.2
EarClippingAlgorithm.....................................................1645.2.3
RecursiveAlgorithm.......................................................167
5.3TriangulationofMonotonePolygons169
5.3.1Linear-TimeAlgorithmforTriangulatingaMonotonePolygon....................170
5.4TriangulationofaPolygonUsingtheSweepLineParadigm175
5.4.1RemovingSPLITVertices....................................................1775.4.2
RemovingMERGEVertices.................................................1785.4.3
AddingEdgestotheBinaryTree............................................1795.4.4
EventHandlinginx-MonotonePolygons......................................1795.4.5
SweepLineStructure......................................................1825.4.6
EventHandling...........................................................1845.4.7
AlgorithmAnalysis.........................................................186
5.5ArtGalleryProblem187
5.6SteveFisk’sProofoftheThree-ColorabilityofPlanarTriangulations188
5.7Exercises189
6DelaunayTriangulation..............................................191
6.1TriangulationofaPlanarPointSet193
6.2Angle-OptimalTriangulation1956.2.1EdgeFlipping.............................................................199
6.3PropertiesofDelaunayTriangulation203
6.4ComputingtheDelaunayTriangulation2056.4.1
Flip-EdgeAlgorithm.......................................................2056.4.2
IncrementalAlgorithm.....................................................2116.4.3
ComparativePerformanceAnalysisofDelaunayTriangulationAlgorithms.........220
6.5Exercises221
7VoronoiDiagrams....................................................223
7.1DefinitionsandBasicPropertiesofVoronoiDiagrams223
7.2AlgorithmsforConstructingVoronoiDiagrams2317.2.1
NaiveApproach..........................................................2317.2.2
RecursiveAlgorithm.......................................................2347.2.3
IncrementalAlgorithm.....................................................2357.2.4
PlaneSweepAlgorithm....................................................2377.2.5
DataStructuresforComputingVoronoiDiagrams..............................2417.2.6
SimulationofFortune’sAlgorithm............................................2457.2.7
ExperimentalEvaluationofVoronoiDiagramConstructionAlgorithms............247
7.3DualityBetweentheVoronoiDiagramandtheDelaunayTriangulation248
7.4TheRelationshipBetweenVoronoiDiagramsand3DConvexHulls249
7.5RecoveringSitesfromaVoronoiDiagram250
7.6VoronoiDiagram-BasedPathPlanningforUnmannedAerialVehicles255
7.7Exercises255
8VisualizationTechniques.......
8.1BasicsofRenderingandVisibilityinThree-DimensionalScenes257
8.2The3DRenderingPipeline:FromTransformationtoIllumination2638.2.1
TransformationMatrices....................................................2638.2.2
PerspectiveProjectionandViewTransformation...............................2668.2.3
ShadingofObjects........................................................268
8.3Painter’sAlgorithm277
8.4Z-BufferAlgorithm278
8.5ModifiedPainter’sAlgorithm282
8.6BSPTreesinTwo-DimensionalSpace2868.6.1ConstructingBSPTreesinthePlane..........................................287
8.7BSPTreesinThree-DimensionalSpace294
8.8Exercises296
9AlgorithmsforSpaceExploration...................................299
9.1One-DimensionalGeometricRangeSearching300
9.2Two-DimensionalSpatialSearch3069.2.1
ProjectionMethod........................................................3079.2.2
GridMethod.............................................................3129.2.3
MethodBasedonBinaryTrees..............................................317
9.3MultidimensionalSearch3219.3.1
GridMethodGeneralization................................................3219.3.2
Generalizationof2DTrees..................................................3219.3.3
ChallengesinHigh-DimensionalSpaces......................................3219.3.4
HeuristicImprovement:AdaptiveSplitting....................................322
9.4Exercises322
10Quadtrees............................................................325
10.1GeometricModelingandThermalSimulationofPCBs326
10.2UniformandNon-UniformMeshes327
10.3QuadtreeStructureConstruction32810.3.1
RecursiveConstructionofaQuadtreeStructureforaPointSet..................330
10.4AlgorithmImplementationforQuadtreeStructureConstruction335
10.5Real-TimeCollisionDetectioninDroneSwarmsUsingQuadtreeStructures34010.5.1
ModelingDronesasPointEntities............................................34010.5.2
QuadtreeBasedCollisionDetectionAlgorithm................................34010.5.3
PythonImplementation....................................................34110.5.4
Conclusion...............................................................344
10.6Exercises344
11RobotMotionPlanning..............................................347
11.1ConfigurationSpacesforRobotMotion349
11.2PointRobot351
11.3ShortestPathSearch356
11.4NaiveImplementationForSeekingShortestPathwithCubicTimeComplexity363
11.5MinkowskiSum366
11.6MinkowskiSum-BasedImplementationofPolygonalRobotPathPlanning374
11.7Exercises377
12AIinComputationalGeometry.....................................379
12.1CoverageOptimization38012.1.1
CameraandSensorPlacementinPolygonalEnvironments.....................38012.1.2
SwarmIntelligenceforGeometricTriangulationOptimization...................38112.1.3
CoveragePathPlanning...................................................382
12.2ImageProcessing38312.2.1FractalCompression.......................................................38312.2.2
Shape-BasedObjectDetection.............................................38412.2.3
MorphologicalOperationsandStructuringElementsGeometry.................385
12.3GeographicInformationSystems38612.3.1
CropMapping...........................................................38612.3.2
SpatialClustering.........................................................38812.3.3
PolygonalMapGeneralization..............................................38912.3.4
TerrainModeling..........................................................390
12.4Bioinformatics39112.4.1MolecularDocking........................................................39212.4.2
ProteinSurfaceRepresentation.............................................39312.4.3
SequenceAlignment......................................................394
12.5ArtificialIntelligence39512.5.1
MotionPlanning,Pathfinding,andObstacleAvoidance........................39512.5.2
Learning-BasedGeometricReconstruction...................................39712.5.3
GeometricObjectClassificationAlgorithms...................................398
Bibliography..........................................................401
Index..................................................................421