Computational Geometry

← Back to Domain-Specific Abstractions by Domain

9 domain-specific abstractions whose origin domain is Computational Geometry.

• Ball Tree — Index points in a metric space with a hierarchy of enclosing balls so triangle-inequality lower bounds prune whole subtrees during exact nearest-neighbor and geometric search.
• Binary space partitioning — A recursive geometric partition that divides a space by hyperplanes into two half-spaces and stores the resulting hierarchy in a binary tree.
• Corner-point grid — A three-dimensional hexahedral grid whose cells are defined by ordered pillars and independently positioned corner points along those pillars.
• Fat object (geometry) — A geometric object whose extent is comparable in every direction under a declared fatness criterion, excluding arbitrarily thin or needle-like shapes and enabling stronger algorithmic bounds.
• Polygon partition — A decomposition of a polygon into nonoverlapping primitive polygons whose union is the original polygon, often optimized by piece count, boundary length or another criterion.
• Relative convex hull — The smallest geodesically convex set containing given points while constrained to remain inside a surrounding polygon or simple closed region.
• Vertex enumeration problem — The computational problem of listing all vertices of a polyhedral or discrete-geometric object from an implicit constraint representation.
• Visibility (geometry) — A geometric relation in which two points see one another when the line segment joining them remains inside free space and avoids declared obstacles.
• Winged Edge — An edge-centered polygon-mesh representation whose endpoint, incident-face, and four neighboring-edge references make local vertex and face incidence directly navigable.