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
4
votes
1
answer
519
views
A brief question about the "Eight Queens" Puzzle
The classical Eight Queens puzzle asks whether it is possible to arrange $ 8 $ queens on an $ 8 \times 8 $ chess board, so that no two queens attack each other.
It is well-known that such ...
- 151k
2
votes
0
answers
185
views
How can I find a basis of $H^0(Y, -K_Y)$ for the del Pezzo surface $Y$ of degree 5?
Consider the surface $X \subset \mathbb{P}^2_{x, y, z}\times\mathbb{P}^1_{t, s}$:
$$
s^3y^2 + t^3yz = (t+s)x^2 + tsxz + t(t^2 +s^2)z^2
$$
over a finite field $k = \mathbb{F}_{2^d}$, $\mathrm{gcd}(d, 6)...
- 1,833
4
votes
2
answers
722
views
Minimum number of rectangles in a polygon
Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.
Example:
Consider the following diagram:
I want to cover maximum shaded ...
- 13k
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 ...
0
votes
1
answer
124
views
Triangle inside the Closed Curve
For any piece wise smooth, simple closed curve $\gamma$ in the Euclidean plane $E^2$ and fix a point $G$ inside the area circled by $\gamma$.
Show: There exists three points $A,B$ and $C$ on the $\...
- 6,337
3
votes
1
answer
295
views
Monotone polygons (and polyhedra) with respect to a point
Dear mathoverflow community,
working on a visualization project I encountered a geometric problem, which I have not yet heard about and am interested in solving algorithmically. However a mere hint ...
- 31
6
votes
1
answer
148
views
Does a minimum area disk that is bounded by a cycle $C$ continuously deform in $R^3$ as $C$ moves in $R^3$?
Let $C_1=(v_1,v_2,\ldots,v_{i-1},v_i)$ and $C_2=(v_1,v_2,\ldots,v_{i-1},v'_i)$ be two cycles that are drawn in $R^3$ in the shape of an unknot (not knotted) with straight line segments as their edges (...
- 415
1
vote
0
answers
368
views
Convex hull of the intersection of nonconvex sets
I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$.
I want to find the convex hull of $...
- 31
2
votes
0
answers
53
views
Facet counting argument for polytopes
Consider a pair of piecewise-linear cobordant $n$ dimensional polyhedra $P_1, P_2$ sitting in $\mathbb{R}^{n+2}$ (with some fixed orientation).
Let $O$ be an $n+1$ dimensional piecewise-linear ...
- 2,689
1
vote
1
answer
253
views
whatever happened to the conference International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)?
I am not sure of a better place to ask this, hopefully someone here knows something...
I've been "away" from computational geometry topics for a bit and thought I'd catch up in some way by checking ...
- 151k
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
5
votes
1
answer
738
views
Graph spectra and topology
This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph.
To give an ...
CommunityBot
- 1
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
4
votes
1
answer
1k
views
How to compute the tangent space of a quotient by a finite group
Let $I\subseteq R:=\mathbb C[x_0,\ldots,x_n]$ be a homogeneous ideal defining a subscheme $X\subseteq\Bbb P^n$. As in my previous question, the permutation group $\mathfrak S_{n+1}$ acts on $R$ by ...
CommunityBot
- 1
8
votes
3
answers
389
views
A simplified Art Gallery Problem in a matrix
Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
- 540
1
vote
0
answers
104
views
connectedness of semi algebraic sets
We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...
- 53
0
votes
0
answers
63
views
Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere
Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...
CommunityBot
- 1
2
votes
1
answer
248
views
Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?
This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
CommunityBot
- 1
1
vote
0
answers
57
views
Covering the annulus of symmetric convex body
Consider a symmetric convex body $A$ in $\mathbb{R}^d$. Now, we draw another object, $A'$, concentric and translated with respect to $A$ and having radius slightly greater than twice to the radius of ...
CommunityBot
- 1
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 3,230
1
vote
0
answers
126
views
cohomology ring of compact submanifolds of Euclidean spaces
Suppose we have a compact $m$-dimensional submanifold $M$ of $\mathbb{R}^N$ and we want to know the cohomology ring $H^*(M;\mathbb{Z})$.
Let $\epsilon>0$ and a $m$-dimensional finite simplicial ...
- 1,990
2
votes
4
answers
651
views
Show that the Minkowski sum of two triangles in 3D is the union of Minkowski sums of each triangle along the other's edges?
I'd like to show (or disprove) the claim that the Minkowski sum of two triangles with vertices in $\mathbb{R}^3$, $A+B$, is equal to the union of the unions of the Minkowski sums of $A$ along all ...
- 96.4k
5
votes
2
answers
1k
views
"Average" Voronoi diagrams without probability?
A plane Poisson process with uniform intensity scatters "sites" about the plane. If I'm not mistaken, in a sense the "average" Voronoi diagram of that set of sites is a honeycomb. I know it's been ...
- 1,862
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
0
votes
0
answers
108
views
conformal deformation with fixed boundaries
For a flat plane with certain boundary, e.g., a rectangular patch, is it possible to conformally displace or deform such patch to a curved bump with exact same boundary? In this thesis, Dr. Keenan ...
- 6,813
1
vote
0
answers
144
views
VC dimension of infinite cones [closed]
What is the VC dimension of infinite $d$-dimensional cones? ( single cones not double).
I would say $2d + 1$ or $O(d^2)$
Does anybody have any reference or ideas?
- 43
0
votes
0
answers
52
views
Efficient sampling from a polytope with large number of contraints [duplicate]
As far as I know, the most popular way to sample from a polytope (in H-representation)
\begin{equation}
\mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\}
\end{equation}
...
CommunityBot
- 1
1
vote
0
answers
162
views
Affine-regular hexagon in convex body
An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...
- 111
-1
votes
2
answers
640
views
Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull) [closed]
Edit : Consider giving a reason for down vote.
In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-...
- 119
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(...
2
votes
1
answer
69
views
Maximal opening angle of a polygon from a point [closed]
I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One ...
- 151k
6
votes
1
answer
239
views
Algorithm that generates a n-simplex that cover n-polytope?
Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?
- 161
3
votes
1
answer
495
views
The circle with minimal radius covering known finite set of points on a plane
Given some points on a plane, how to determine the circle with minimal radius covering all these points?
- 151k
6
votes
2
answers
335
views
Do computational geometers use Lagrange multipliers?
Can anyone point me to an example of a problem that (more or less) originated in computational geometry whose solution requires the use of Lagrange multipliers (or Kuhn-Tucker conditions, or dual ...
- 96.4k
0
votes
1
answer
575
views
Detect perimetral edges of a polygon [closed]
I'm developing a building editor. Users can draw rooms by adding angles (vertices of the room) with a left click. Clicking on an existing angle closes the room and fills the floor by using the ...
CommunityBot
- 1
5
votes
1
answer
261
views
Do random triangulation edge-flips maintain randomness?
Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...
- 37.7k
6
votes
1
answer
5k
views
Finding the vertices of a convex polyhedron from a set of planes
I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...
CommunityBot
- 1
1
vote
0
answers
537
views
Epsilon-net of operator norm ball around Identity
Suppose I look at the set of matrices which are invertible and satisfy
$$
\left\|A-Id\right\|_{op}<r
$$
for some $r<1$, where $Id$ is the $n\times n$ identity matrix. An $\epsilon$-net of such ...
- 205
4
votes
2
answers
2k
views
Breaking a rectangle into smaller rectangles with small diagonals
Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
- 30.1k
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 ...
CommunityBot
- 1
5
votes
2
answers
153
views
Expressing a convex Polytope as a sublevel set of a function
Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to \...
- 800
2
votes
0
answers
697
views
Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin
Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them?
Background:
Thanks to Will Jagy ...
CommunityBot
- 1
5
votes
2
answers
557
views
What are the applications of Voronoi diagrams in pure mathematics? [closed]
Voronoi diagrams have interesting mathematical properties and applications in algorithms and modeling. But what are its applications in pure mathematics? For example, what theorems can be proved using ...
- 378
6
votes
1
answer
239
views
Fractional Helly for more than one piercing
Fractional Helly Theorem says the following:
For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n \...
- 196
4
votes
2
answers
390
views
Construct polygon/polyhedron containing all points not externally visible w.r.t given polygon/polyhedron?
Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron?
In 2D, we could consider polygons. For ...
CommunityBot
- 1
4
votes
1
answer
400
views
Finding the "top" or "bottom" vertex of a simplex
A vertex $v$ of a simplex in $\mathbb{R}^n$ is a "top" vertex if there exists a point $p \neq v$ in the simplex with $v \ge p$ (i.e. $v_1 \ge p_1$, ... , $v_n \ge p_n$). Similarly, $v$ is a "bottom" ...
CommunityBot
- 1
5
votes
3
answers
4k
views
Minimum distance between two arbitrary circles in space?
What is the minimum distance between two arbitrary circles in space?
I am working out the problem with Maxima, but I am surprised by how complicated this rapidly turns out to unfold for such a "...
CommunityBot
- 1
3
votes
1
answer
2k
views
Trilateration problem
When trying to develop an algorithm for a program, I got with the following problem:
Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...
CommunityBot
- 1
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
2
votes
0
answers
126
views
Intersecting balls with convex regions and a bisector thereof
This question is related to my previous posting
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex region in the plane and let $s$ be the shortest ...
CommunityBot
- 1