Intereting Posts

Does really convergence in distribution or in law implies convergence in PMF or PDF?
Can one show a beginning student how to use the $p$-adics to solve a problem?
Axis of Symmetry for a General Parabola
What are the epimorphisms in the category of Hausdorff spaces?
How can this be proved $\lim_{x\to\infty}(f(x)+f'(x))=l$
Integral solutions of hyperboloid $x^2+y^2-z^2=1$
Elementary solution to the Mordell equation $y^2=x^3+9$?
Find the real number $x$ represented by continued fraction $$
how to find a complex integral when the singular point is on the given curve
$\lim_{x\to a^{-}} f(x) =\lim_{x\to a^{+}} f(x) =L$
Is there a name for the curve $t \mapsto (t,t^2,t^3)$?
lacunary sum of binomial coefficients
Is taking projective closure a functor?
Is there a nonnormal operator with spectrum strictly continuous?
Examples of prime ideals that are not maximal

I’ve got a specific problem which I’ll try to describe as clearly as possible.

I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular sub-regions that are described in terms of their 4 vertices, ie {(x1, y1), (x1, y2), (x2, y1), (x2, y2)}, so that these regions form ‘occlusions’ on the plane. These regions don’t overlap, but they can form more complex polygons when different-sized rectangles adjacent to each other appear joined.

here’s an illustration:

- Algorithm to generate an uniform distribution of points in the volume of an hypersphere/on the surface of an hypersphere.
- Solving very large matrices in “pieces”
- Execution time of function
- Non-revealing maximum
- Algorithms for finding the multiplicative order of an element in a group of integers mod m
- Polynomial Question

I am interested in the space between these shapes, and how to define the space in the same way the occlusions are defined, that is as a set of rectangles. In particular I want the definition optimised so that the space is described using the smallest possible number of rectangles. For example, an incomplete rendering might look like this:

Can anyone suggest a way forward with this? How can I have the original set of vertices (describing the black rectangles) generate the ‘complementary’ set of vertices (red rectangles) such that the number of red rectangles is minimal?

I suspect it’s a variation of a ‘packing problem’, but I have a feeling it might be fairly simple…

- How to find the third coordinate of a right triangle given 2 coordinates and lengths of each side
- Expected value when die is rolled $N$ times
- Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method
- Largest prime factor of 600851475143
- HINT for summing digits of a large power
- Horse Race question: how to find the 3 fastest horses?
- Number of integer solutions: $x^2 + y^2 + z^2 = N$
- Polynomial Question
- Algorithm for constructing primes
- Characterizing a real symmetric matrix $A$ as $A = XX^T - YY^T$

This problem has been studied in the 1980’s. You can find it named the problem of finding

a minimum rectangle partition of an orthogonal polygon with holes. In the older literature, sometimes “orthogonal” is replaced with “rectilinear.” If you wrap your black rectangles with the minimum bounding box, then you have converted it to an orthogonal polygon with holes.

I believe the first result was by Lipsky in 1979, but I am not finding that

paper. Here is a somewhat later paper:

“Partitioning rectilinear figures into rectangles.” 1988. (ACM link)

Although many problems superficially analogous to this are NP-hard,

this rectangle-partition problem can be solved in

$O(n^{5/2})$ time for a polygon of $n$ vertices in total.

The algorithms depend on finding a maximum independent set of the

intersection graph of certain chords in the polygon.

(Added

a

partition can be found in $O(n \log \log n)$ time.

- Counting the number of integers $i$ such that $\sigma(i)$ is even.
- The myth of no prime formula?
- How does “If $P$ then $Q$” have the same meaning as “$Q$ only if $P$ ”?
- Assumption about elements of the empty set
- Equation of the Plane
- Trying to prove that a group is not Cyclic
- Convex hull of extreme points
- Showing that a collection of sets is a $\sigma$-algebra: either set or complement is countable
- Non-differentiability in $\mathbb R\setminus\mathbb Q$ of the modification of the Thomae's function
- Singular values of transpose same?
- Test for convergence with either comparison test or limit comparison test
- Looking for Proofs Of Basic Properties Of Real Numbers
- What books are recommended for learning calculus on my own?
- Why is this limit said to equal some value rather than approach that value?
- Calculate the curvature of a parametrized curve