Skip to main content

All Questions

Filter by
Sorted by
Tagged with
8 votes
3 answers
389 views

A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
Yijun Yuan's user avatar
6 votes
1 answer
424 views

Probability of intersecting a rectangle with random straight lines

We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
Penelope Benenati's user avatar
5 votes
1 answer
255 views

Counting points above lines

Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
H A Helfgott's user avatar
  • 20.2k
4 votes
1 answer
519 views

A brief question about the "Eight Queens" Puzzle

The classical Eight Queens puzzle asks whether it is possible to arrange $ 8 $ queens on an $ 8 \times 8 $ chess board, so that no two queens attack each other. It is well-known that such ...
Boggie Georgiev's user avatar
4 votes
1 answer
1k views

Finding integer points on an N-d convex hull

Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is ...
Michael Hoffman's user avatar
3 votes
2 answers
333 views

Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
Rodrigo Castro's user avatar
2 votes
1 answer
270 views

Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...
oren harlev's user avatar