Computational Geometry邓俊辉25September20261:21AM
Computational Geometry 邓俊辉 25 September 20261:21 AM
Computational GeometryWhatCGStudies国algorithms&datastructuresforgeometricproblemsdiscrete&finitegeometricobjectsonearea of theoretical computerscienceHandbookofDiscrete&ComputationalGeometry6categories52topicsJunhui Deng,Tsinghua Computer
Computational Geometry ☞ What CG Studies − algorithms & data structures for geometric problems − discrete & finite geometric objects − one area of theoretical computer science ☞ Handbook of Discrete & Computational Geometry − 6 categories − 52 topics Junhui Deng, Tsinghua Computer
Geometric nlgorithmpGeometricsearch国point locationrangequerylsearchProximitynearestneighborqueryDecomposition/meshgeneration国triangulation/trapezoidalizationVisibilitytest国intersection/collisiondetection/transversaEGeometricoptimization/approximationMEC/MES/.greedy triangulationJunhui Deng,Tsinghua Computer
Geometric Algorithms ☞ Geometric search − point location − range query/search ☞ Proximity − nearest neighbor query ☞ Decomposition / mesh generation − triangulation / trapezoidalization ☞ Visibility test − intersection / collision detection / transversal ☞ Geometric optimization / approximation − MEC / MES / . − greedy triangulation Junhui Deng, Tsinghua Computer
Data StruetureArrangement/configuration国lattice/k-set/k-level/envelope/zonotope/.Convexhull国polyhedron/polytopeSubdivisionEVoronoi diagramDelaunaytriangulation/MWT/greedytriangulationtrapezoidal mapquadtree/octree/kd-tree/rangetree/segmenttree/BsPtree/Junhui Deng,Tsinghua Computer
Data Structures ☞ Arrangement / configuration − lattice / k-set / k-level / envelope / zonotope / . ☞ Convex hull − polyhedron / polytope ☞ Subdivision − Voronoi diagram − Delaunay triangulation / MWT / greedy triangulation − trapezoidal map − quadtree / octree / kd-tree / range tree / segment tree / BSP tree / . Junhui Deng, Tsinghua Computer
methodologieyReductionGDuality国GeometrictransformationEDecomposition&hierarchizationRandomization/derandomization国ApproximationParallelization国Junhui Deng,Tsinghua Computer
Methodologies ☞ Reduction ☞ Duality ☞ Geometric transformation ☞ Decomposition & hierarchization ☞ Randomization / derandomization ☞ Approximation ☞ Parallelization Junhui Deng, Tsinghua Computer