Algorithms

Algorithm Families Overview

LIRiAP implements three main solver families and one exact solver.

Family Comparison

Family	Primary Objective	Strict Containment	Boundary Expansion	Best For
Approximation	Fast area-focused search	No (not certified)	No	Quick candidates, exploratory analysis
Skeleton	BCRS-free skeleton-guided solver	Yes (unless fallback enabled)	Yes (SDF)	Fast certified containment, skeleton-based candidate generation
BCRS	Full contained + fit improvement	Yes (unless fallback enabled)	Yes (SDF)	Maximum accuracy via vertex-coordinate grid + SDF
Axis-Aligned	Exact fixed-axis solve	Exact (vertex-coordinate)	N/A	Fastest for axis-aligned problems, exact solution

The contained family is superseded — skeleton covers the same use-case with higher fill rate and better speed.

Performance (baseline, 1 worker)

Algorithm	TOP_K	Time @290 (s)	Mean Fill%
Approx Fast	1	6.98	TBD
BCRS Fast	1	7.21	~53.5%
Skeleton	1	8.41	~53.5%
Axis-Aligned LIR	n/a	11.81	35.87
BCRS	1	10.82	~54.0%
BCRS Fast	3	15.54	55.27
Skeleton	3	24.64	54.96
BCRS	3	26.33	55.74

top_k=1 makes BCRS Fast and Skeleton competitive with approximation times while maintaining certified containment.

Algorithm Matrix

Algorithm	Variant	Containment Semantics	Expansion	Complexity
Approximation Standard	Approx	Not certified	No	O(n + (m+s180)g² + (p+1)g²)
Approximation Fast	Approx	Not certified	No	Same as Standard
Skeleton	Skeleton	Certified / best-effort	SDF-guided	O(150·N + k·(g² + n log n))
BCRS	BCRS	Certified / best-effort	SDF-guided	O(n + (m+s90)g² + k(pg² + t(g² + n log n + nu + n) + n))
BCRS Fast	BCRS	Certified / best-effort	SDF-guided	O(n + (m+s90)g² + k((p+4)g² + t(n log n + nu + n) + n))
Axis-Aligned LIR	Exact	Exact (vertex-coordinate)	N/A	O(n²)

Execution Modes

All algorithms support multiple execution modes via parameters:

Mode	N_WORKERS	USE_CHUNKING	Characteristics
Serial	1	False	Single-threaded, no overhead
Parallel	>1	False	Per-feature parallel execution
Chunked	>1	True	Chunk-based parallel, better for cancelling

Speed / Accuracy Slider

The top_k parameter controls the number of candidates refined:

• top_k=3 (default): explores edge histograms / skeleton regions for maximum fill rate
• top_k=1: skips candidate ranking, uses the single strongest candidate — 2-3× faster with ~1-2% fill loss

This makes BCRS Fast with top_k=1 as fast as approximation Fast while returning certified contained results — the strongest practical trade-off available.

Selection Guide

Start: Do you need strict containment?
├─ No → Approximation family (fast candidates)
│
└─ Yes → Do you need axis-aligned rectangles?
    ├─ Yes → Axis-Aligned LIR (exact, fastest for this case)
    │
    └─ No → Choose seed generation method
        ├─ Medial-axis skeleton → Skeleton family
        │   └─ BCRS-free, fastest certified solver with top_k=1
        │
        └─ Vertex-coordinate grid → BCRS family
            ├─ Need speed → BCRS Fast (top_k=1 matches approx speed)
            └─ Maximum accuracy → BCRS (top_k=3)

Axis-Aligned LIR

For fixed-orientation (axis-aligned) rectangles, use Axis-Aligned LIR:

• Exact solution (vertex-coordinate precision)
• O(n²) complexity
• Supports convex, concave, with/without holes
• Optional rotation parameter for tilted axis
• Fastest algorithm for axis-aligned problems (11.81s @290)

See Axis-Aligned LIR for details.