Computational Complexity

Complexity must identify the task, algorithm, arithmetic precision, and output representation. This page distinguishes costs rather than assigning a single complexity to all GRG methods.

Scalar Kernel Evaluation

Given local geometric ratios, the current circle kernels require a fixed number of arithmetic operations. Obtaining the ratios has its own cost. A binary-bisection evaluation performs a number of refinement stages proportional to the binary depth; square-root cost depends on precision and implementation.

Explicit Geometry

Generating and storing all sector nodes has a cost proportional to the output count. Streaming may reduce storage, but does not remove output work.

Raster and Volume Tasks

Boundary drawing, disk filling, surface generation, and voxel filling have different output sizes. Their cost statements must specify whether every output element is generated.

Comparisons

Report setup, precomputation, precision, memory, and runtime at equal achieved accuracy under the benchmark protocol. Earlier repeated cost models have been consolidated here.