All Questions
Tagged with computational-geometry mg.metric-geometry
162
questions
8
votes
0
answers
175
views
Placing triangles around a central triangle: Optimal Strategy?
This question has gone for a while without an answer on MSE (despite a bounty that came and went) so I am now cross-posting it here, on MO, in the hope that someone may have an idea about how to ...
- 7,771
1
vote
1
answer
128
views
An algorithm to arrange max number of copies of a polygon around and touching another polygon
A related post: To place copies of a planar convex region such that number of 'contacts' among them is maximized
Basic question: Given two convex polygonal regions P and Q, to arrange the max ...
- 5,827
6
votes
2
answers
179
views
Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π.
Given a convex polygon, how does one algorithmically find the point (...
- 5,827
1
vote
0
answers
64
views
Algorithm to generate configurations with kissing number 12
That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...
- 111
1
vote
1
answer
61
views
To maximize the volume of the polyhedron resulting from perimeter-halvings of a convex polygonal region
We add one more bit to Forming paper bags that can 'trap' 3D regions of max surface area (note: some possibly open related questions are also in the comments following the answer to above ...
- 5,827
1
vote
0
answers
90
views
A claim on the largest area circular segment that can be drawn inside a planar convex region
This post adds a little to To find the longest circular arc that can lie inside a given convex polygon
A circular segment is formed by a chord of a circle and the line segment connecting its endpoints....
- 5,827
0
votes
0
answers
62
views
Comparing partitions of a given planar convex region into pieces with equal perimeter and pieces of equal width
We continue from Cutting convex regions into equal diameter and equal least width pieces. There we had asked for algorithms to partition a planar convex polygon into (1) $n$ convex pieces of equal ...
- 5,827
2
votes
0
answers
65
views
Computational complexity of exact computation of the doubling dimension
Given a finite metric space $X$, the doubling constant of $X$ is the smallest integer $k$ such that any ball of arbitrary radius $r$ can be covered by at most $k$ balls of radius $r/2$. The doubling ...
0
votes
1
answer
61
views
Robustness of doubling dimension to small perturbations
Let $M$ be a metric space. Then the doubling dimension of $M$, denoted $\dim M$, is defined to be the minimum value $k$ such that every ball in $M$ of radius $r$ can be covered by at most $2^k$ balls ...
0
votes
0
answers
50
views
Optimal packing and covering of a triangle with squares
We continue from Another variant of the Malfatti problem.
Given a triangle T and a number n, how to cover it with n squares (of possibly different dimensions) such that the sum of the areas (...
- 5,827
4
votes
2
answers
201
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
- 142
3
votes
0
answers
178
views
Algorithm to dissect a polygon into a minimum amount of rectangles, conditioned on a maximum overlap
I have the following problem, I have a problem regarding concave polygons. I want to write code to cover any polygon with a minimum amount of rectangles that are allowed to overlap and have no fixed ...
- 31
1
vote
1
answer
56
views
On largest convex m-gons contained in a given convex n-gon where m < n
This post is the inside-out variant of On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, how to find the max area convex m-gon Q ...
- 5,827
0
votes
0
answers
91
views
On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, will the least area convex m-gon Q that contains P be such that an edge of Q coincides with an edge of P (in other words Q cannot be such that P ...
- 5,827
2
votes
1
answer
130
views
Planar convex region maximizing the difference in 'orientation' between its smallest containing rectangle and largest contained rectangle
We say a rectangle has orientation $\theta$ if the vector from its center to the middle of its shortest side (parallel to the longest side) has some angle $\theta$ with X axis.
Consider a planar ...
- 5,827