Questions tagged [computational-geometry]
Using computers to solve geometric problems. Questions with this tag should typically have at least one other tag indicating what sort of geometry is involved, such as ag.algebraic-geometry or mg.metric-geometry.
503 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
1
answer
149
views
Existence of element $(x_0,y)$ in a set of common zeros for all $(x_0,y)$ satisfying system of inequalities
Let $f_1,f_2,\cdots,f_n,g_1,g_2\cdots,g_m\in \mathbb{R}[x,y]$, then define the affine variety and semi-affine variety as follows:
$V(f_1,f_2,\cdots,f_n):=\{(x,y)\in\mathbb{C}^2: f_1(x,y)=f_2(x,y)=\...
CommunityBot
- 1
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
0
votes
0
answers
72
views
Reflections of Voronoi diagrams
I wonder if something similar to the following fact is known, and I would greatly appreciate any references.
Let $t_1, t_2, \ldots, t_N$ be unit vectors in $\mathbb{R}^n$.
Let $S$ denote the unit ...
- 1
17
votes
2
answers
2k
views
Efficiently determine if convex hull contains the unit ball
Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
- 221
1
vote
0
answers
37
views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function
$$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$
Can we find all the ...
- 11
0
votes
0
answers
37
views
Constructing a minimum-volume outer approximation polytope with fewer facets
I am tackling the following problem:
Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
- 63.9k
0
votes
0
answers
25
views
Is there a name for a spanner graph that only considers distance to a root node?
A $t$-spanner graph of a set of points $\{p_i\}$ in the plane is a graph $G = (V, E)$ such that for any pair of vertices $p_i, p_j \in V$, the shortest path distance $d_G(p_i, p_j)$ in $G$ is at most $...
- 4,049
14
votes
2
answers
637
views
Tarski-Seidenberg for strict inequalities and bounded quantification
This theorem says that quantifiers over real variables can be eliminated from classical first order formulae built from equations and inequalities between polynomials with rational coefficients, ie in ...
CommunityBot
- 1
11
votes
2
answers
3k
views
Algorithm for embedding a graph with metric constraints
Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
- 13.2k
1
vote
1
answer
242
views
Finding generators of symmetric cones
I have a bunch of vectors $\mathbf v_i$ in $\mathbb R^n$. I would like to consider the cone $C$ spanned by these vectors, together with all the other vectors that can be obtained by permuting the ...
CommunityBot
- 1
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 ...
- 151k
2
votes
2
answers
213
views
Bounding the length difference of two curves given the Fréchet distance between them
Given two simple, closed, convex, planar curves $C_1$ and $C_2$, let their lengths be $\ell_1$ and $\ell_2$, respectively, and their Fréchet distance be $d_f$. We are trying to bound $|\ell_1 - \ell_2|...
CommunityBot
- 1
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
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 ...
- 60.5k
1
vote
0
answers
13
views
Complexity of counting maximal points in query orthogonal rectangles
The problem stated in the title is the following: given an $n\times n$ binary matrix $M=\left(m_{rc}\right)$ report the number of $1$'s in a query rectangle
$[i,j]\times[h,k]$
$1\le i\lt j\le n,\, 1\...
- 13.2k
1
vote
0
answers
22
views
Calculating an optimal scaling factor for Delaunay triangulations
consider a finite set $\mathcal{P}(x,y)=\lbrace(x_1,y_1),\dots,\,(x_n,y_n)\rbrace$ of points in the Euclidean plane and let $\mathrm{DT}(x,y)$ be the Delaunay triangulation of $\mathcal{P}(x,y)$
...
- 13.2k
9
votes
0
answers
205
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,831
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 ...
- 12.9k
3
votes
1
answer
431
views
Detecting a PL sphere and decompositions
Question 1. A PL $n$-sphere is a pure simplicial complex that is a triangulation of the $n$-sphere. I'm looking for a computer algorithm that gives a Yes/No answer to whether a given simplicial ...
- 903
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 ...
- 151k
4
votes
2
answers
1k
views
Polyline averaging
I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them. The input lines do not loop.
...
- 1
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
5
votes
0
answers
475
views
Closest vertices of an AABB to a ray in n-dimensions
I came across this computational geometry problem and have not been able to find a satisfactory solution for it. A ray is known to originate from within an n-dimensional hypercube (AABB) in any ...
- 81
1
vote
0
answers
142
views
Explicit computation of Čech-cohomology of coherent sheaves on $\mathbb{P}^n_A$
$\newcommand{\proj}[1]{\operatorname{proj}(#1)}
\newcommand{\PSP}{\mathbb{P}}$These days I noticed the following result of (constructive) commutative algebra, which I think is probably well known ...
- 12.9k
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
3
votes
0
answers
83
views
Practical way of computing bitangent lines of a quartic (using computers)
Are there known practical algorithms or methods to calculate the bitangent lines of a quartic defined by $f(u,v,t)=0$ in terms of the 15 coefficients? Theoretically you can set up $f(u,v,-au-bv)=(k_0u^...
- 101
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
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
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 ...
- 2,858
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, ...
- 60.5k
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 (...
- 60.5k
0
votes
0
answers
32
views
Set of enclosed convex polyhedra in a graph
Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...
- 1
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
1
vote
0
answers
65
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 ...
- 3,065
0
votes
0
answers
65
views
Computational tasks resulting from Chern-Weil theory
I have recently learned Chern-Weil theory for smooth and complex manifolds, as well as surrounding material on cohomology with integral coefficients.
I am curious what computational tasks are ...
CommunityBot
- 1
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 ...
- 151k
2
votes
0
answers
117
views
Folding polygons into 'vessels'
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf
Define an vessel as a convex polyhedron with one face removed - in other words, a vessel can be converted into a ...
- 5,979
2
votes
0
answers
95
views
To find the longest circular arc that can lie inside a given convex polygon
Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P.
For some P, the optimal subset will be a full circle; otherwise, a single arc ...
- 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
0
votes
1
answer
75
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 ...
3
votes
0
answers
85
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 ...
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
4
votes
2
answers
335
views
Software for finding conjugates in the braid group
The conjugacy problem for the braid group was solved by Garside, and gives an algorithm for determining whether two braids are conjugate. Since this algorithm is rather tedious, I was wondering if ...
- 68.9k
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 ...
- 701
2
votes
1
answer
271
views
Irreducibility of an explicit complex projective variety
Let $Y\subset \mathbb P^n_\mathbb C$ be a subvariety defined by a series of homogeneous polynomials $f_1, \ldots, f_t$. Is there an effective way to determine the irreducibility of $Y$ as an algebraic ...
- 704
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
2
votes
0
answers
147
views
Graph Laplacians, Riemannian manifolds, and object collisions
To preface this question, I am a part-time game developer and full-time optimization fiend.
I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
- 63.9k
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