{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Refinement Trees and Parallelization with Space-Filling Curves" ] }, { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Exercise 1: Hilbert-Order Encoding of a Quadtree" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Given a domain with an obstacle (see the tutorial worksheet), we want to run a certain simulation on this domain.\n", "In order to obtain accurate results it is enough to have a fine mesh only near the boundary of the obstacle. \n", "Everywhere else the grid can be as coarse as possible.\n", "\n", "a)\n", " Use the following strategy to refine the given square domain: If a square cell contains a boundary of the obstacle, subdivide this square into four equal subsquares. \n", " Perform at most four subdivisions, in other words, the maximum depth of the corresponding quadtree is four.\n", " Sketch the resulting grid on the figure with obstacle provided in the tutorial worksheet.\n", "\n", "b)\n", " Draw a corresponding quadtree of the refined domain.\n", "\n", "c)\n", " Sequentialize the spacetree grid by using a Hilbert space-filling curve.\n", " Start with the non-terminal $H$.\n", " Use the following grammar rules for Hilbert orders on quadtrees:\n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "
 $H \\longleftarrow (A \\uparrow H \\rightarrow H \\downarrow B)$ $H \\longleftarrow \\bullet$ $A \\longleftarrow (H \\rightarrow A \\uparrow A \\leftarrow C)$ $A \\longleftarrow \\bullet$ $B \\longleftarrow (C \\leftarrow B \\downarrow B \\rightarrow H)$ $B \\longleftarrow \\bullet$ $C \\longleftarrow (B \\downarrow C \\leftarrow C \\uparrow A)$ $C \\longleftarrow \\bullet$