33

What you described is Voronoi diagram. Here is an excerpt from Wikipedia. In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean plane. In this case each site $p_k$ is simply a point, and its corresponding Voronoi cell $R_k$ consists of every point in the Euclidean plane whose distance to $...


16

I will try to show this problem is NP-hard, by reduction from $\text{Planar-}3\text{-SAT}$. Reduction from $\text{Planar-}3\text{-SAT}$ Some basic Gadgets Gadgets are internal configurations of geometry that will allow us to construct gates for use in a circuit, to which we will reduce $\text{Planar-}3\text{-SAT}$. 4X3-gadget This gadget has two valid ...


15

Let me answer your question partially for the hexagram case. You can make the following tiling $\hskip1.2in$ By this you will cover 12/14=6/7 of the plane (count the triangles in the dashed quadrilateral). Is this optimal? I would think so. Although I am not giving a proof I will provide some arguments. One can ask, how good we can fill the space (...


15

Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case. Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation). However, you ...


12

Since I created this I probably can explain it best ;-): the first step is to calculate an image segmentation which will combine small areas of similar colors into bigger chunks. The tolerance values of that segmentation will influence how big the biggest circles can become (higher tolerance => bigger areas => bigger circles) You proceed by processing each ...


12

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or ...


11

This is known as the Ham-Sandwich theorem: Given two measurable objects in $2$-dimensional Euclidean space, it is possible to divide each of them in half with a line. Note: Convexity is not needed. And $\mathbb{R}^2$ can be replaced by $\mathbb{R}^d$ with "line" replaced by a $(d{-}1)$-dimensional hyperplane.             ...


10

Yes, this can be $O(n \log n)$ time. Build a Voronoi diagram for $T$. Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in. The center of that cell is the point $t \in T$ that is closest to $s$. You can build a Voronoi diagram in $O(n \log n)$ time, and each query (find the cell containing $s$) can be done in $O(\log ...


9

Create a Voronoi diagram on the $n$ disk centers in $O(n\log n)$ time. Intersect it with the rectangle in $O(n)$ time. Now you have a set of convex shapes, thus the furthest point away from the center of the disk inside the cell is a vertex on the cell. Compute the furthest point for each cell can be done in $O(n)$ time. If for all of them, it is within $r$,...


9

One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that ...


9

Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts. Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\...


9

I assume we are working in $\mathbb{R}^n$. First of all, observe that one regular $n-$simplex effectively determines all the others. In fact, if $S_1, S_2$ are two sets of points in $\mathbb{R}^n$ that satisfy the regularity condition, then they can be obtained from each other by composing at most an isometry and an homothetic transformation of the affine ...


8

There is an extension of half-edge in any dimension, called darts in combinatorial maps. There are two packages in CGAL allowing to use these combinatorial maps in any dimension (see here for combinatorialMaps and here for LinearCellComplex). You can use this data structure to represent any Quasi manifold orientable subdivided 3D object. Quoting from CGAL ...


8

An old paper I coauthored establishes that the covering problem is polynomial for a polygon without holes, and NP-complete with holes. We showed that a key underlying graph is chordal. Please note: the algorithm is polynomial in the number $N$ of unit squares in the polygon, $O(N^{3/2})$. "Covering orthogonal polygons with squares." L. J. Aupperle and H....


7

This is the smallest enclosing circle problem, and can be solved in linear time. Also, these slides describe a randomized algorithm that runs in expected linear time.


7

This point is known as the geometric median, also known as the 1-median. Apparently, there is no simple algorithm for computing the geometric median. Instead, one must use some kind of numerical approximation. Wikipedia mentions Weiszfeld's algorithm, which appears to be a kind of iterative descent algorithm, and cites other more sophisticated algorithms. ...


7

Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here. The first step of the Grahm Scan is to sort the points in a set based on the angle made with the X axis when drawing a line through the point and the lower-right point of the set. This seems to solve the ...


7

Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small. Let $y_1,\ldots,y_d$ be its neighbors. Draw a small circle of radius $\epsilon$ around $x$, and "project" each $y_i$ to a point $z_i$ on the circle: the point $z_i$ is just the ...


6

Theorem 1. For every polygon with edge length sequence $a_1,\ldots,a_m$, there exist a convex polygon with same edge length sequence. Proof. Here. Definition. $a_1,\ldots,a_n$ be $n$ non-negative reals. It satisfies (strict) $n$-gon inequality if $2a_j < \sum_{i=1}^n a_i$ for all $j$. Theorem 2. The sequence $a_1,\ldots,a_n$ is a sequence of edge length ...


6

Restating the problem. As far as I can tell, your system is equivalent to the following: $$c_1 x_1 + \dots + c_n x_n = N$$ subject to the constraints $$0 \le x_1, \dots, x_n \le 1.$$ Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are ...


6

A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters. You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).


6

There's an enormous amount of work on data structures and algorithms for this sort of problem. I suggest you start by reading the general literature on this problem. Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem. Those techniques are applicable to your problem. ...


6

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search: Procedure NN(node), given query q if(node is leaf) Search all points, in node, update current best else {internal node} if( cut_coord(q) <= node's cut-value ) NN(left-child) if( cut-coor(q) + ...


6

For a slightly more general way of looking at this, what you want to do is equivalent to saying you can reconstruct the convex hull from the orderings induced by projections onto the coordinate axes. To see you can't do this, just observe that for three points $a$, $b$, and $c$, knowing that $a < c < b$ in both projections doesn't let you figure out ...


6

This is a classic problem in computational geometry, called Polygon Inclusion Problem. Further, you are considering its special case --- Convex Inclusion. In chapter 4 of this thesis by Michael lail Shamos 1978, you will find that: Generally, Theorem 4.2 (Page 92): Whether a point is interior to a simple $n$-gon can be determined in $O(n)$ time, without ...


6

No. You can't do better than $\Theta(n^2)$ in the worst case. Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) Then you can't do better than to examine every edge. In particular, if there is any edge you have not examined, then an adversary could choose the length of ...


6

Exhaustively tracing the movement of the ball is the easiest to program, and also not too bad on efficiency grounds. You should keep a hash table of all states of the ball that have been seen before (where the state of a ball is the grid square it is in, and which direction it is heading); if you see it repeat a past state, then you know it will loop ...


6

Basically this is shortest path problem in polygon with holes. There is no constraint in taking $E_i$ as a path of negligible width. If you just want to connect internal holes to outside boundary without caring about the path length, then just take any point on the boundary of interior hole and calculate a path to any point on the outer boundary. I don't ...


6

If you polytope is convex, this answer should work. Otherwise you can always do rejection sampling: Sample a point from the bounding box, check whether it's inside the polygon. That gets really slow for high dimensions and "unboxy" polytopes though, because the bounding box potentially has a huge volume compared to the region you're interested in.


Only top voted, non community-wiki answers of a minimum length are eligible