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.
169 questions with no upvoted or accepted answers
26
votes
0
answers
908
views
Where to submit this work with several unusual features?
I appreciate that questions about where to submit are generally considered off-topic, but I hope that the unusual features of the present case may make it acceptable.
I have put a monograph on github ...
- 56.9k
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 ...
- 8,481
14
votes
0
answers
261
views
Dividing a convex region to minimize average distances
Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
- 4,049
11
votes
0
answers
234
views
When is cohomology of a finitely presented dg-algebra computable?
Given a smooth affine variety $X$ defined over $\mathbb{Q}$, its singular cohomology is isomorphic to the algebraic de Rham cohomology, which is the cohomology of the complex $\Omega_X^0\to\Omega_X^1\...
- 3,772
10
votes
0
answers
441
views
A new $\ell_p$-metric on the hyperspace of finite sets?
Let $(X,d)$ be a metric space and $Fin(X)$ be the family of all non-empty finite subsets of $X$. For every $n\in\mathbb N$ the elements of the power $X^n$ are thought as functions $f:n\to X$ where $n:=...
- 41.9k
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
9
votes
0
answers
290
views
Computer algebra tools for finding real dimension of an algebraic variety
I have a system of polynomial equations with the unknowns being real numbers. The set of solutions is infinite. What software can I use to compute the real dimension of the solution set?
The CAD-based ...
- 175
8
votes
0
answers
229
views
Nearest point to a real algebraic set
Suppose I have a compact bounded real algebraic (eventually: or analytic or semialgebraic or semianalytic set) $V \subset \mathbb R^3$ and a point $x\in\mathbb R^3 \setminus V$. How much do we know ...
- 2,275
7
votes
0
answers
122
views
Does the problem of recognizing 3DORG-graphs have polynomial complexity?
A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
- 4,535
6
votes
0
answers
219
views
How big a box can you wrap with a given polygon?
Question: Given a convex polygonal region, how does one find the box (rectangular parallelopiped) of maximum volume that can be wrapped with this region? While wrapping, if needed, some portions of ...
- 5,979
6
votes
0
answers
157
views
On cutting disks from planar regions
Question: Given a planar region $R$ of unit area and an integer $n$, to cut $n$ circular disks (their sizes need not be equal) such that the highest fraction of $R$ is taken off.
A simple greedy ...
- 5,979
6
votes
0
answers
237
views
Complexity of scissors congruence?
Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
- 13.9k
6
votes
0
answers
114
views
Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces
Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...
- 161
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
5
votes
0
answers
167
views
Computing sums with linear conditions quickly
Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...
- 20.2k
5
votes
0
answers
85
views
special classes of ideals (eg. toric) that admit faster Buchberger algorithm?
I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-...
- 1,221
5
votes
0
answers
87
views
Problem to efficiently compute the Volume of $d$ anchored 4D cuboids
An easy still unsolved special case of Klee's measure problem with applications in multiple objective optimization is described in the following.
Let $[\vec a_1,\vec b_1],\dots,[\vec a_n,\vec b_n]$ ...
- 4,535
5
votes
0
answers
350
views
Are nearby points in an algebraic curve necessarily connected?
I would like a result of the following form:
For every algebraic curve $C$ in $\mathbb{R}\mathbf{P}^{n-1}$, there exists an
explicit and easy-to-compute $\epsilon=\epsilon(C)>0$ such that ...
- 7,633
5
votes
0
answers
273
views
Can this set of equations be solved explicitly for algebraic curves?
In my recent work I stumbled upon a set of two equations. I'm interested in solving by eliminating auxiliary variable "$z$" and getting algebraic curve in terms of $x$ and $y$ given by the zero locus ...
- 243
5
votes
0
answers
1k
views
Reach of manifold vs. $C^k$-manifold
The reach $\tau_M$ of a manifold $M$ is the largest number such that any point at distance less than $\tau_M$ from $M$ has a unique nearest point on $M$.
This concept seems quite related to the local ...
- 151k
5
votes
0
answers
2k
views
Find the axis of symmetry in a point cloud
I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
- 151
5
votes
0
answers
193
views
Determining N d-points yielding equal sums of Euclidean distances from M s-points
Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...
- 51
5
votes
0
answers
214
views
Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell
Given an $n \times n$ grid with unit grid cells, and one point from the interior
of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
user71114
5
votes
0
answers
783
views
Intuition behind minimizing the Dirichlet energy of a mapping
What does minimizing the Dirichlet energy of a mapping $\Phi$ achieve intuitively?
Roughly it is the integral (or sum, if discrete) of $|\nabla \Phi(\;)|^2 dV$, with $V$ the volume.
So is it, in some ...
- 151k
5
votes
0
answers
309
views
Upper bounds on art gallery problems using independent witnesses
Given a polygon $P$, the art gallery problem looks to find a smallest set of points that sees all of $P$. One way of bounding the number of guards necessary (from below) is to find a largest set of ...
- 1,182
4
votes
0
answers
123
views
Cylindrical Decomposition vs Morse decomposition
Suppose I have a polynomial Morse function $f: \mathbb{R}^n \to \mathbb{R}$. Consider the ideal $I(\nabla f)$ generated by the partial derivatives $\partial_i f$, and assume that the real zero-set of ...
- 505
4
votes
0
answers
458
views
Generating random polygons from a given triangulation of points
Given a triangulation $T$ of a planar set point $S$, we would like to randomly generate a polygon (hamiltonian cycle) $P$.
However, it has been proved that Hamiltonian Circuit Problem on maximal ...
- 61
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
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 ...
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
3
votes
0
answers
95
views
Fast numerical integration of $\int_{[0,\:1)^d}\left|f_x(y)-g(y)\right|^p\:{\rm d}y$ for varying $x\in[0,1)^d$
Let $k\in\mathbb N$ and $y_1,\ldots,y_k\in[0,1)^d$ with $$\frac1k\sum_{i=1}^kh(y_i)\approx\int_{[0,\:1)^d}h(y)\:{\rm d}y\tag1$$ for every nice enough function $h:[0,1)^d\to\mathbb R$.
Now let $p\ge1$, ...
- 167
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
3
votes
0
answers
144
views
Hemisphere containing the maximum number of points scattered on a sphere
Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...
- 127
3
votes
0
answers
285
views
Explicit computations of finite covers of genus one curves with two points of ramification
I have an explicit genus one curve $E$ with two points $p_1$ and $p_2$ on it and am looking for an explicit degree seven cover $X\to E$ with ramification precisely over $p_i$, with a single preimage ...
- 5,186
3
votes
0
answers
260
views
What is the VC-dimension of regular convex k-gons in the plane?
Recall the relevant definitions:
Let $H$ be a family of sets in $\mathbb{R}^d$. The intersection of $H$ with a point set $C$ is defined as $H\cap C = \{h\cap C\mid h\in H\}$. The VC-dimension of $H$ (...
- 131
3
votes
0
answers
141
views
Optimal intersections between planar convex regions
Here is an earlier discussion that could be related:
On comparing planar convex regions of equal perimeter and area
We are broadly interested in placing two given planar convex regions so that the ...
- 5,979
3
votes
0
answers
51
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
- 3,079
3
votes
0
answers
175
views
Cutting convex polygons into triangles of same diameter
This question continues from: Cutting convex regions into equal diameter and equal least width pieces
Definitions: The diameter of a convex region is the greatest distance between any pair of points ...
- 5,979
3
votes
0
answers
106
views
finding a good term order for grobner basis
What are the tricks to pick a "good" monomial order to find a Grobner basis for a given ideal?
By good I mean one in which the final Grobner basis has a simple expression in terms of the ...
- 1,435
3
votes
0
answers
84
views
Signed triangulations of simplicial polyhedra
Let $\partial S$ be the boundary of a compact polyhedron $S\subset\mathbb{R}^3$, assumed to be generic, in the sense that every face of $S$ is a triangle, and so that there are exactly two triangles ...
- 14k
3
votes
0
answers
133
views
Lower bound on the intersection of $\ell_1$ $n$-balls
Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ in $\ell_1$ norm, with distance $d$ and radius $R$.
Is there a lower bound on the volume of the intersection between the two n-balls? (assuming the ...
- 301
3
votes
0
answers
61
views
Biggest Cartesian Product Included in a Real Plane Curve
Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
- 351
3
votes
0
answers
100
views
Optimally placing rectangles with obstacles
I am struggling with a fairly simple and natural geometric optimization problem, but I have not been able to find an obvious canonical method for solving it:
I am given a collection of $m$ axis-...
- 4,049
3
votes
0
answers
63
views
Exact Value of a Constant Related to the Quickhull Algorithm
What is the exact value of the infinite sum
$$ \sum_{n=1}^{\infty}n2^n\sin\left(\frac{\pi}{2^n}\right)\left(1-\cos\left(\frac{\pi}{2^n}\right)\right)$$
That constant is related to the Quickhull ...
- 13.2k
3
votes
0
answers
234
views
Uniqueness of Riemann Constant Vector Solution
Let $X$ be a compact, genus $g$ Riemann surface (given as the desingularization and compactification of a plane algebraic curve), $J(X)$ its Jacobian, and $A : X \to J(X)$ the Abel map
$$A(P) = \left(...
3
votes
0
answers
169
views
Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)
Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $...
- 41
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
3
votes
0
answers
58
views
Find shift direction for min overlap area of 2 polygons
I have 2 arbitrary polygons (concave or convex) with certain overlap.
Now there is some relative shift between these 2 polygons (vector s with a constant length).
I want to find the direction of s ...
- 31
3
votes
0
answers
129
views
Computing with Graphs in Surfaces
I asked this question yesterday on math.stackexchange, but the only response so far hasn't really addressed the question, so I thought I'd cross-post it.
I am currently working on a research project ...
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