All Questions
Tagged with computational-geometry discrete-geometry
146 questions
1
vote
0
answers
68
views
To partition a triangle into $n$ convex pieces with sum of number of sides over all pieces maximized
This post is a variant on To cut a triangle into $n$ $p$-sided polygonal regions.
Question: Given a positive integer $n$, a triangular region is to be cut into $n$ convex pieces so that the sum over ...
- 5,979
1
vote
0
answers
58
views
On partitioning the surface of a convex solid into geodesically convex equal area regions
We refer to a subset S of the surface of a convex solid C as geodesically convex if the shortest path along the surface of C joining any two points in S lies entirely within S (and if there are more ...
- 5,979
4
votes
1
answer
356
views
Left and right halves of convex curve
Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even.
A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
- 214
3
votes
1
answer
130
views
Why is the Vietoris–Rips complex $\operatorname{VR}(S, \epsilon)$ a subset of the Čech complex $\operatorname{Čech}(S, \epsilon\sqrt{2})$?
$\DeclareMathOperator\Cech{Čech}\DeclareMathOperator\VR{VR}$I am reading Fasy, Lecci, Rinaldo, Wasserman, Balakrishnan, and Singh - Confidence sets for persistence diagrams (see here for a version of ...
1
vote
1
answer
103
views
Algorithm to find largest planar section of a convex polyhedral solid
We add a bit more on shadows and planar sections following On a pair of solids with both corresponding maximal planar sections and shadows having equal area . We consider only polyhedrons.
Given a ...
- 5,979
1
vote
1
answer
134
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,979
1
vote
1
answer
178
views
Inside-out dissections of solids -2
We record some general questions based on
Inside-out dissections of solids
Inside-out dissections of a cube
Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
- 5,979
1
vote
0
answers
93
views
Inside-out dissections of a cube
Ref:
Inside-out polygonal dissections
Inside-out dissections of solids
Definitions: A polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 5,979
5
votes
1
answer
269
views
Is the maximal packing density of identical circles in a circle always an algebraic number?
There is a lot of interest in the maximal density of equal circle packing in a circle. And I thought that knowing whether or not the solution is always algebraic or not would be useful.
My original ...
- 53
1
vote
1
answer
104
views
Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon
This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
Given a convex n-gon, ...
- 5,979
6
votes
2
answers
189
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,979
1
vote
0
answers
96
views
An algorithm to decide whether a convex polygon can be cut into 2 mutually congruent pieces
This post is based on the answer to this question: A claim on partitioning a convex planar region into congruent pieces
A perfect congruent partition of a planar region is a partition of it with no ...
- 5,979
1
vote
1
answer
68
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,979
1
vote
0
answers
91
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,979
0
votes
0
answers
67
views
Comparing partitions of a given planar convex region into pieces with equal diameter 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,979
1
vote
0
answers
91
views
Dissection of polygons into triangles with least number of intermediate pieces
This wiki article: https://en.wikipedia.org/wiki/Wallace%E2%80%93Bolyai%E2%80%93Gerwien_theorem shows the dissection of a square into a triangle via 4 intermediate pieces. It appears easy to form a ...
- 5,979
1
vote
0
answers
41
views
Are there rectangles that can be cut into non-right triangles that are pair-wise similar and pair-wise non-congruent?
We generalize the questions of Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
Can any rectangle be cut into some finite number of triangles that ...
- 5,979
1
vote
0
answers
92
views
Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces
A (non square) rectangle can obviously ...
- 5,979
2
votes
0
answers
73
views
Is this an actual solution for centroidal Voronoi tiling, or just a visual approximation? [closed]
For the capstone project at the end of my graduate Data Science studies in late 2022, I needed an algorithm that would converge to something close to centroidal Voronoi tiling, while tiling contiguous ...
- 121
4
votes
2
answers
219
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
0
votes
0
answers
63
views
Bounds for the Dispersal Problem in convex regions
We add a bit to: Bounds for minimax facility location in a convex region
Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on ...
- 5,979
1
vote
0
answers
89
views
Bounds for minimax facility location in a convex region
An earlier question: Facility location on manifolds
A possibly related earlier post: Cutting convex regions into equal diameter and equal least width pieces - 2
The minimax facility location problem ...
- 5,979
3
votes
0
answers
226
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
61
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,979
0
votes
0
answers
93
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,979
2
votes
1
answer
132
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,979
1
vote
1
answer
78
views
To optimally wrap convex laminae with paper
Ref: On folding a polygonal sheet, Multi-layered wrapping of polyhedra
Basic intent: to wrap a given convex planar lamina with a convex sheet of non-stretchable paper (such that every point on both ...
- 5,979
1
vote
0
answers
34
views
On partitioning convex polygonal regions in area ratio $t : (1-t)$ where $0<t<1/2$ with least length of cut
Question: Given a convex n-gon P. How can we efficiently find the partition of P into 2 pieces with areas in the some given ratio $t : (1-t)$ where $0<t<1/2$ such that the length of cut is ...
- 5,979
1
vote
2
answers
124
views
Are there variants of Euclidean Steiner Tree problem that are known to be in P?
Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have ...
- 5,979
1
vote
1
answer
73
views
Partitioning polygons into obtuse isosceles triangles
Ref:
Partitioning polygons into acute isosceles triangles
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
https://math.stackexchange.com/questions/1052063/...
- 5,979
1
vote
0
answers
58
views
Covering a unit square with odd number of equal area triangles - optimally
We add a bit to this post: Cutting off odd numbers of equal area triangles from a unit square
Question: Given an odd integer n, how does one cover the unit square completely with n equal area ...
- 5,979
2
votes
0
answers
126
views
Checking existence of a non-crossing Hamiltonian path in geometric graphs
I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are ...
- 1,305
17
votes
1
answer
580
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...
- 48.9k
1
vote
0
answers
82
views
Inside-out dissections of polygons - a generalization
Definitions (Inside-out polygonal dissections): a polygon P has an inside out dissection into P' if P′ is congruent to P and the perimeter of P becomes interior to P' and so the perimeter of P' is ...
- 5,979
5
votes
3
answers
542
views
If a polyhedron in $\mathbb{R}^3$ has local intersections, does it also have more global intersections?
Consider a simplicial complex $K$. A piecewise linear map $f: K \to \mathbb{R}^n$ is an almost-embedding if $f(\sigma) \cap f(\tau) = \emptyset$ for any two disjoint simplices $\sigma,\tau$ in $K$.
...
- 141
1
vote
1
answer
127
views
Smallest trapeziums containing a given convex n-gon
Question: Given a planar convex $n$-gon $C$, to find the smallest area / smallest perimeter trapezium (trapezoid) - a convex quadrilateral with at least one pair of mutually parallel edges - that ...
- 5,979
3
votes
0
answers
65
views
Cutting triangles into triangles with equal longest side
This post elaborates on a specific instance of Cutting convex polygons into triangles of same diameter .
Question: For any integer n, can any triangle be cut into n non-degenerate triangles all of ...
- 5,979
0
votes
1
answer
51
views
What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?
The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...
- 413
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 $\...
- 20.2k
3
votes
1
answer
111
views
Constrained morphing of polygons
This post continues 'Constrained morphing' of planar convex regions
If an $m$-gon $P_m$ is to be morphed (altered continuously) into an $n$-gon $P_n$ with same area and perimeter, can one ...
- 5,979
2
votes
1
answer
84
views
'Constrained morphing' of planar convex regions
Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints.
Qn: If $C_1$ and $...
- 5,979
1
vote
0
answers
46
views
Computational hardness of a discrete generalized rectangle packing problem
I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
1
vote
0
answers
110
views
Upper bound on the diameter of a convex lattice n-gon with a given area
Given the area $A$ of a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
- 206
1
vote
0
answers
78
views
Triangulation of polygons with all triangles having a common angle
Following Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles, we record another triangulation question.
Question: Given an n-vertex polygonal region ("n-...
- 5,979
6
votes
2
answers
215
views
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
Definition: Let us refer to obtuse triangles with the largest angle strictly above a given cutoff value as 'strongly obtuse' - the definition is parametrized by the cutoff value. Likewise, strongly ...
- 5,979
2
votes
0
answers
197
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
- 2,993
1
vote
0
answers
30
views
Partitioning convex n-gons into least number of equal area convex quadrilaterals
This post adds a bit to Partitioning convex polygons into quadrilaterals of equal area and perimeter
Question: How does one achieve the partition of any given convex n-gon into the least number of ...
- 5,979
11
votes
1
answer
410
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
- 17k
1
vote
0
answers
62
views
What are some other methods for partitioning an n-dimensional space based on a set of points in that space?
So this is a very general question, but I'm curious if there are any other methods for partitioning an n-dimensional space based on the location of a set of points, either randomly chosen or specified,...
- 11
2
votes
1
answer
92
views
Determining if a polygon is convex using relations on orientation of each ordered triple of points
I am reading a paper by Szekeres and Peters on computing the 17-point case of the Erdős–Szekeres conjecture. The conjecture states that the minimum number of points in the plane (in general position, ...
- 123