Complexity

Computational Complexity Analysis

Formal time and space complexity analysis for all LIRiAP algorithms.

Symbols

Symbol	Meaning
n	Total polygon vertices (exterior + holes)
g_coarse	Coarse grid size (GRID_COARSE)
g_fine	Fine grid size (GRID_FINE)
k	Candidate count kept for refinement (TOP_K)
m	Edge-guided initial angle candidates (<=12 in Contained/BCRS, <=10 in Approximation)
s90	Fallback sweep size: ceil(90 / a), where a = ANGLE_STEP
s180	Approximation fallback sweep size: ceil(180 / a)
p	Brent objective evaluations (maxiter=60 where explicitly set)
t	Stage 4-5 angle trials per candidate (<=4 in BCRS, <=2 in BCRS Fast)
nu	BCRS cell count: (|X| - 1) x (|Y| - 1), max 89401 (300x300)

Primitive Solver Costs

Uniform Grid Solver
$$T_{grid}(g) = O(g^2), M_{grid}(g) = O(g^2)$$

BCRS Variable-Pitch Solver
$$T_{bcrs} = O(n \log n + \nu), M_{bcrs} = O(n + \nu)$$

Implementation guard: if |X| > 300 or |Y| > 300, BCRS is skipped (seed fallback).

CABF Expansion
$$T_{cabf} = O(n)$$

Certification + Best-Effort Shrink
$$T_{cert} = O(n), T_{shrink} = O(n)$$

Axis-Aligned Solvers (Alt/Amenta, Daniels et al.)
$$T_{axis} = O(n^2), M_{axis} = O(n^2)$$

Per-Feature Complexity

Generic Pipeline
$$T_{feature} = T_{angles} + T_{stage1} + T_{refine} + T_{cert/fallback}$$

BCRS-Family
$$T_{feature,BCRS} = T_{angles} + T_{stage1} + T_{refine} + T_{expand} + T_{cert/fallback}$$

Algorithm Worst-Case Complexity

Algorithm	Time (single feature)	Memory
Approximation Standard	O(n + (m+s180)g_coarse^2 + (p+1)g_fine^2)	O(max(g_coarse^2, g_fine^2))
Approximation Fast	Same as Standard	Same
Contained Standard	O(n + (m+s90)g_coarse^2 + k((p+2)g_fine^2 + n))	O(max(g_coarse^2, g_fine^2))
Contained Fast	O(n + (m+s90)g_coarse^2 + k(pg_coarse^2 + g_fine^2 + n))	O(max(g_coarse^2, g_fine^2))
BCRS	O(n + (m+s90)g_coarse^2 + k(pg_coarse^2 + t(g_fine^2 + n log n + nu + n) + n))	O(max(g_fine^2, nu))
BCRS Fast	O(n + (m+s90)g_coarse^2 + k((p+4)g_coarse^2 + t(n log n + nu + n) + n)), t<=2	O(max(g_coarse^2, nu))
Axis-Aligned LIR	O(n^2)	O(n^2)

Fast Variant Speedup

Contained
$$\Delta \approx p(g_{fine}^2 - g_{coarse}^2)$$ per candidate saved

BCRS
$$\Delta \approx (4-2)(n \log n + \nu) + 4g_{fine}^2 - 4g_{coarse}^2$$

Default Parameters

Family	g_coarse	g_fine	k	ANGLE_STEP
Approximation	40	100	1	5
Contained/BCRS	40	120	3	5

Derived: s180=36, s90=18, 40^2=1600, 100^2=10000, 120^2=14400

Dominant Term Estimates

Algorithm	Grid Units
Approx Standard/Fast	(10+36)x1600 + (60+1)x10000 = 683,600
Contained Standard	(12+18)x1600 + 3x(60+2)x14400 = 2,726,400
Contained Fast	(12+18)x1600 + 3x(60x1600 + 14400) = 379,200
BCRS	(12+18)x1600 + 3x(60x1600 + 4x(14400 + 89401)) = 1,581,612
BCRS Fast	(12+18)x1600 + 3x((60+4)x1600 + 2x89401) = 891,606
Axis-Aligned LIR	O(n^2)

Verification

Using baseline 5406-feature wall times (N_WORKERS=1):

Comparison	Expected	Measured	Result
Approx Fast vs Standard	~equal	125.93s vs 127.25s	Consistent
Contained Fast vs Standard	Fast < Std	226.05s < 574.13s	Consistent
BCRS Fast vs BCRS	Fast < Std	445.01s < 772.05s	Consistent

The model captures intra-family speed relations well.

Scaling Behavior

All scaling exponents ~1.0 (linear). BCRS and Axis-Aligned show negative speedup with multithreading (slower).

---

Navigation

• Home | Installation | Algorithms | Approximation | Contained | BCRS | Axis-Aligned | Performance | Foundations | Parameters | Folder Layout | Usage