Matematické Fórum

Hertas · 01. 03. 2016 22:14

Dobrý večer přeji,

zabývám se úlohou, kdy dostanu zadanou oblast $\Omega \subset \mathbb{R}^2$ a nějakou implicitně zadanou křivku $C=C(x, y)$ . Oblast $\Omega$ "rozřežu" na $n\times m$ podoblastí $\omega_{i,j}, i \in \{1, 2, ..., n\}, j \in \{1, 2, ..., m\}$ takových, že $\omega_{i, j} = [x_{i}, x_{i+1}]\times[y_{j}, y_{j+1}]$ a body $x_1, ..., x_{n+1}, y_1, ..., y_{m+1}$ jsou dělící body oblasti $\Omega$ .

Nyní chci pro každou oblast $\omega_{i,j}$ algoritmicky rozhodnout, zda $C \subset \omega_{i,j}$ či $C \not \subset \omega_{i,j}$ .

Triviální řešení (hrubou silou), které se okamžitě nabízí je postupně za x volit hraniční body oblasti a zkoumat, či je splněna rovnice $C(x,y)=0$ pro y z dané oblasti a pokud ne tak celý postup opakovat pro y.

Ve dvou dimenzích by složitost byla ještě přijatelná, bohužel bych úlohu chtěl časem řešit ve více dimenzích a složitost úlohy roste exponenciálně v závislosti na dimenzi. Ideální by byl nějaký algoritmus s nanejvýš lineární složitostí :)

Budu rád za každý nápad

kaja.marik · 02. 03. 2016 12:56

Takze potrebuji $C \subset \omega_{i,j}$ , tj. ze dana oblast obsahuje celou krivku $C$ a nikde jinde uz zadny kousicek neni. To se podle me nepovede jenom zkoumanim uvnitr te oblasti $\omega_{i,j}$ , protoze rovnice $0=C(x, y)$ muze definovat sedm kruznic ruzne pohazenych po $\Omega$ . Tj. pro oblast $\omega_{i,j}$ nejde algoritmicky rozhodnout to co potrebujete, musi se prochazet cela $\Omega$ . Jsou nejake dalsi predpoklady na $C(x,y)$ , ktere toto vylouci?

Tak jenom takovy napad, netum jak by to bylo se slozitosti: pokud jsou funkce slusne hladke, mohlo by pomoci hledani absolutniho maxima a minima funkce $C(x,y)$ . Pokud mají stejné znaménko, neni v oblasti ani kousicek krivky $C(x,y)=0$ . A algoritmy na to hledani maxima a minima by mohly byt nejake dostatecne sofistikovane.

Hertas · 02. 03. 2016 17:41 — Editoval Hertas (02. 03. 2016 21:21)

Tady jsem se samozřejmě špatně vyjádřil. Zajímá mě $C \subset \omega_{i,j}$ při restrikci $C = C(x,y) \wedge x,y \in \omega_{i,j}$ .

Slovně řečeno: mám-li implicitně zadanou křivku a zvolím-li součin intervalů $[x_1,x_2]\times[y_1,y_2]$ , zajímá mě, zda křivka prochází tímto součinem intervalů.

Derivace se mi jeví jako relativně složitá záležitost (nemám páru jak to naprogramovat bez aproximací :)), ale určitě bude ve vyšších dimenzích mít menší složitost než řešení co napadlo mě.

Matematické Fórum

#1 01. 03. 2016 22:14

Křivka a oblast

#2 02. 03. 2016 12:56

Re: Křivka a oblast

#3 02. 03. 2016 17:41 — Editoval Hertas (02. 03. 2016 21:21)

Re: Křivka a oblast

Zápatí