Suppose $f:[0,1]\times[0,1]\mapsto X$ is a continuous function. Show that $[0,1]\times[0,1]$ can partitioned into rectangles s.t $f(R_i)\subseteq U_k$


Suppose $ f:[0,1]\times[0,1]\mapsto X$ , is a continuous function where $ X$ compact and connected subset of $ \mathbb{R}^n$ . Show that $ [0,1]\times[0,1]$ can partitioned into rectangles $ R_i$ such that $ f(R_i)\subseteq U_i$ where $ U_i\in C$ a cover for $ X$ .

My attempt at a proof:

Choose a cover $ C$ of $ X$ .

Since $ f$ is a continuous function on a compact set it is uniformly continuous.

Thus there exists a $ \delta>0$ such that $ \forall \epsilon>0$ and $ \forall x,y\in [0,1]\times[0,1]$ if $ \vert x-y\vert<\delta$ then $ \vert f(x)-f(y)\vert<\epsilon$

Choose $ R_i$ with side lengths $ \frac{\delta}{\sqrt{2}}$ , idea is to guarantee the elements in the rectangles are $ \delta$ close. Then the image $ f(R_i)$ can be contained in a ball $ B_\epsilon(f(x))$ for any point $ f(x)\in f(R_i)$ for any $ \epsilon>0$ . Since the open cover is fixed we can choose $ \epsilon=\max d(x,y)$ for any $ x,y\in U_i$ for any $ U_i\in C$ . So that $ f(R_i)\subseteq B_\epsilon(f(x))$ for some $ f(x)\in f(R_i)$ and $ B_\epsilon(f(x))\subseteq U_i$

Does this seem correct? I think there are some issues with my choice of $ \epsilon$ .

Fitting $\frac1n\times\frac1{n+1}$ rectangles into the unit square

Consider the set of rectangles $ r_n | n \in \Bbb N$ such that rectangle $ r_n$ has shape $ \frac1n\times\frac1{n+1}$ . The total area composed by one copy of each $ r_n$ as $ n$ ranges from $ 1$ to infinity is $ 1$ . Call that set of rectangles $ S$ .

In Concrete Mathematics it is speculated that you can fit all the rectangles in $ S$ into a unit square, without overlap of any interior area. It is also speculated (by the second author) that they can’t all be fit, and it is presented as a research problem.

I have a computer-based approach which could potentially decide the issue if you can’t fit them (but won’t provide a proof if they can fit). In particular, it seems to indicate that if you add the restriction that the rectangles (ordered by area) are forced to alternate long-side-vertical and long-side-horizontal, you come to an impasse.

But since the volume I saw it in is 25 years old, I’m wondering, before implementing and error-checking and optimizing the method for arbitrary placement, whether this question has, in the intervening years, been resolved.

So my question is

Is it known whether $ S$ can be packed into a unit square, without overlap?

Arithmetic that corresponds to combinatorial rectangles and cylinder intersections?

Definable subsets of $ \mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets.

In communication complexity the interpretation is more on intersection and union of combinatorial rectangles or complements of combinatorial cylinder intersections which does not seem to be as nice as what comes from geometric interpretation of Presburger.

Is there an arithmetic that corresponds to definable sets in communication complexity?

Would it be reasonable to expect something?

Highest stack of rectangles

Suppose we have a set of $ n$ dimensional rectangles $ R = \{(x_{i,1}, \ldots, x_{i,n}), i \in 1 \ldots k\}$ . We want to create the highest stack in say the first dimension such that each side of the rectangles form a monotonically increasing sequence. More formally from the $ l-tuples$ satisfying this

$ $ \max_{l: (j_{1}, \ldots, j_{l}), j_{i} \in 1 \ldots k, j_{q} = j_{p} \iff q = p}{\forall q \in 1 \ldots l – 1, \forall p \in 1 \ldots n: x_{j_{q}, p} < x_{j_{q + 1}, p}} $ $

take the one with the maximal $ \sum_{i = 1}^{l}{x_{j_{i}, 1}}$ or just simply calculate this maximal value.

What’s the algorithmic complexity of this? For $ n = 1$ we can think of this as a weighted LIS. Is there a better approach than just sorting it on the first dimension and trying to find the longest increasing sub sequence for all dimensions?

Drawing consecutive rectangles with an algorithm

I have an assignment to draw rectangles that get larger and larger each time I draw them. Just like shown below. I’ve labeled them TL = Top Left, TR = Top Right, BL = Bottom Left, BR = Bottom Right. The smallest boxes are 8 pixels by 8 pixels. From this drawing I pulled these algorithms for each box. Where n represents the level you are drawing. Level 0 is the inside set of four and grows out by 1.

TL = (x-n(8), y - n(8)) TR = ((x + 8) - (n*8), y - n(8)) BL = (x - n(8), y - (n+1)(8)) BR = ((x+8)+(n*8), (y+8)-(n*8)); 

My real questions is this. I feel like I can combine these algorithms into something smaller but i’m new to this type of thinking. This is the first Computer Science Class I’ve taken that required me to do this type of thinking. Do you have any suggestions?

From these algorithms I wrote this code in Java.

    public static void drawRectangle(Graphics g, int xCenter, int yCenter, int levelsNeeded){     //all squres are based off an 8 pixel system.  I use this to shift things around ALOT.     final int CHANGECONSTANT = 8;      int width = 8;     int height = 8;     int dcg = 1; //Dimension Change Factor      Point origin = new Point(xCenter -= CHANGECONSTANT, yCenter -= CHANGECONSTANT); //Sets Origin to top left of inner most set of squares      for (int level = 0; level < levelsNeeded; level++)     {         g.setColor(Color.GRAY);         //Top Left         g.fillRect(          (int)origin.getX()-(level*CHANGECONSTANT), // XCord          (int)origin.getY()-(level*CHANGECONSTANT), // YCord          width, //width. This stays at 8 for all iterations          height*dcg);//height. This gets multiplied by odd factors each time          //Draw outline          g.setColor(Color.BLACK);         g.drawRect(          (int)origin.getX()-(level*CHANGECONSTANT), // XCord          (int)origin.getY()-(level*CHANGECONSTANT), // YCord          width, //width. This stays at 8 for all iterations          height*dcg);//height. This gets multiplied by odd factors each time          g.setColor(Color.GRAY);         //Bottom Left         g.fillRect(          (int)origin.getX()-(level*CHANGECONSTANT), //XCrod          (int)origin.getY()+((level+1)*CHANGECONSTANT), //YCord          width*dcg, //width. This gets multiplied by odd factors each time           height); //height. This stays at 8 for all iterations         g.setColor(Color.BLACK);         //Draw Outline         g.drawRect(          (int)origin.getX()-(level*CHANGECONSTANT), //XCrod          (int)origin.getY()+((level+1)*CHANGECONSTANT), //YCord          width*dcg, //width. This gets multiplied by odd factors each time           height); //height. This stays at 8 for all iterations           g.setColor(Color.WHITE);         //Top Right         g.fillRect(          ((int)origin.getX()+CHANGECONSTANT)-(level*CHANGECONSTANT), //XCord          (int)origin.getY()-(level*CHANGECONSTANT), //YCord          width*dcg,//width. This gets multiplied by odd factors each time           height);//height. This stays at 8 for all iterations          //Draw Outline         g.setColor(Color.BLACK);         g.drawRect(          ((int)origin.getX()+CHANGECONSTANT)-(level*CHANGECONSTANT), //XCord          (int)origin.getY()-(level*CHANGECONSTANT), //YCord          width*dcg,//width. This gets multiplied by odd factors each time           height);//height. This stays at 8 for all iterations          g.setColor(Color.WHITE);         //Bottom Right         g.fillRect(          ((int)origin.getX()+CHANGECONSTANT)+(level*CHANGECONSTANT), //Xcord          ((int)origin.getY()+CHANGECONSTANT)-(level*CHANGECONSTANT), //Ycord          width,//width. This gets multiplied by odd factors each time           height*dcg);//Height. This stays at 8 for all iterations.          //Draw Outline         g.setColor(Color.BLACK);         g.drawRect(          ((int)origin.getX()+CHANGECONSTANT)+(level*CHANGECONSTANT), //Xcord          ((int)origin.getY()+CHANGECONSTANT)-(level*CHANGECONSTANT), //Ycord          width,//width. This gets multiplied by odd factors each time           height*dcg);//Height. This stays at 8 for all iterations.           dcg += 2; //Increment DCG by two at end of each loop      } }  

Here is what my final product looks like right now. Disregard the triangle shapes that a different method that calls the first one multiple times.

This is my first quarter learning Java and i’m new to programming.

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

Initial Problem enter image description here

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work.

Final Structure

Possible steps Possible steps

Example of a Real World problem Real Word problem

Annotations on Preview, why do rectangles now put text in weird orientations?

When creating a rectangle in Preview sometimes text orientation is weird enter image description here

It appears that this is something happening since Mohave… when drawing a rectangle using the pen tool (Sketch) and doing a rectangle now the text sometimes appear in a weird orientation, let’s say for instance upside down…

  • When does this orientation happen?
  • What steps can I do to make it not happen?
  • If it happens, can I rotate the rectangle?