Delbeläggning

  I matematik är en underbeläggning en uppsättning icke-överlappande rutor av R⁺ . En delmängd X av Rⁿ kan approximeras av två underbeläggningar X⁻ och X⁺ så att X⁻ ⊂ X ⊂ X⁺ .

I R¹ är rutorna linjesegment, i R² rektanglar och i Rⁿ hyperrektanglar. En R²- underbeläggning kan också vara en " oregelbunden plattsättning med rektanglar", när den inte har några hål.

Infästning av den streckade uppsättningen X mellan två underbeläggningar. Röda lådor: inre underbeläggning. Rött och gult: yttre underbeläggning. Skillnaden , yttre minus inre, är en gränsapproximation .

Lådor har fördelen av att de är mycket lätta att manipulera av datorer, eftersom de utgör hjärtat av intervallanalys . Många intervallalgoritmer ger naturligtvis lösningar som är vanliga underbeläggningar.

Vid beräkning är en välkänd tillämpning av subbeläggning i R² Quadtree-datastrukturen . I bildspårningssammanhang och andra tillämpningar är det viktigt att se X⁻ som topologisk inre , som illustreras.

Exempel

 
De tre figurerna till höger nedan visar en approximation av mängden X = {( x ₁ , x ₂ ) ∈ R ² | x
² ₁ + x
² ₂ + sin( x ₁ + x ₂ ) ∈ [4,9]} med olika noggrannhet. Uppsättningen X⁻ motsvarar röda rutor och uppsättningen X⁺ innehåller alla röda och gula rutor.

Underbeläggningar som fäster ett set med låg upplösning

Underbeläggningar som fäster samma uppsättning med en måttlig upplösning

Underbeläggningar som fäster setet med hög upplösning

I kombination med intervallbaserade metoder används underbeläggningar för att approximera lösningsuppsättningen av icke-linjära problem, såsom inversionsproblem . Underbeläggningar kan också användas för att bevisa att en uppsättning som definieras av icke-linjära ojämlikheter är vägansluten , för att tillhandahålla topologiska egenskaper hos sådana uppsättningar, för att lösa problem med pianoförflyttare eller för att implementera uppsättningsberäkning.