All Questions
Tagged with computational-geometry covering
8 questions
1
vote
0
answers
111
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,979
2
votes
1
answer
192
views
On some optimal containers of a set of points on the 2D plane
Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find
the smallest semicircular region (semidisk) that contains the points
the smallest ...
- 5,979
3
votes
1
answer
212
views
How to cover n sites with the smallest number of fixed radius balls?
Given $n$ "data points" in $d$ (Euclidean) space
$$\mathbf{x}_j \in \mathbb{R}^d, \text{ for } j \in \{1,\dots,n\}$$
how does one find the smallest integer $m$ such that there exists $m$ "centre ...
- 723
2
votes
0
answers
486
views
Finding good high-dimensional sphere coverings in Euclidean space
Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...
- 733
3
votes
1
answer
429
views
Finding a minimum covering of a polygon with interesting shapes
After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
- 3,549
4
votes
1
answer
2k
views
Algorithms for covering a rectilinear polygon using the same multiple rectangles
Sorry for the crossing-posting: original post is here
All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
- 143
12
votes
2
answers
11k
views
Covering a polygon with rectangles
I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...
1
vote
1
answer
3k
views
Covering an arbitrary polygon with minimum number of squares
I have a problem whereby, given an arbitrary polygon with any number of points, I need to cover the whole area by a number of fixed size squares. I can easily find a set of squares which covers the ...
- 51