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
2
answers
141
views
Incremental structure of a delaunay triangulation
This would probably be considered a reference request, as I would imagine it has been studied extensively in earlier work. Say I have a collection of distinct points $X = \{x_1,\dots,x_n\}$ in the ...
- 13.2k
4
votes
3
answers
2k
views
How to find the minimum number of hyperplanes to define a convex hull?
I have the following problem:
I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq ...
CommunityBot
- 1
3
votes
1
answer
462
views
Number of isomorphism classes of triangulations of a convex polygon
The number of triangulations of a convex $n$-gon is $C_{n-2}$ the $n-2$nd Catalan number. What I am wondering, is if there is a way to enumerate the isomorphism types of these as graphs? I am ...
- 37.7k
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 ...
CommunityBot
- 1
4
votes
1
answer
2k
views
Algorithms for covering a rectilinear polygon using the same multiple rectangles
Sorry for the crossing-posting: original post is here
All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
CommunityBot
- 1
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 ...
- 3,549
17
votes
1
answer
874
views
An NP-hard $n$ fold integral
We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\...
CommunityBot
- 1
5
votes
1
answer
566
views
Biggest ball included in an intersection of balls
I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
- 61.9k
1
vote
2
answers
431
views
Higher dimensional convex hull
Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as $E(v)=...
- 278
3
votes
1
answer
199
views
The discrete theory of compressible fluids dynamics
I am working on the discrete theory of compressible fluids dynamics, i.e., numerically solving and simulating the compressible fluids , we are interested in the way using discrete exterior calculus, ...
- 188k
2
votes
2
answers
5k
views
Projection of a point to a convex hull in d dimensions
Hi,
I've got n points in d dimensions (typically n is around 30k-60k and d is 5 or 6). I'm using qhull to calculate the Delaunay triangulation and the convex hull of the set of points.
You can ...
CommunityBot
- 1
3
votes
1
answer
2k
views
Find longest segment through centroid of 2D convex polygon?
Given a 2D convex polygon P and its centroid C, how do I find the longest line segment passing through C, where the endpoints of the segment lie on the boundary of P?
Intuitively I imagine there ...
- 151k
11
votes
3
answers
960
views
Algorithms in Invariant Theory
Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$.
In chapter 4.6 of his book "Algorithms in Invariant ...
- 195
0
votes
0
answers
585
views
Determining the simplices in freudenthal triangulation
HI,
I have a doubt on Freudenthal Triangulation. I want to partition a simplex into finer simplices.
The FT gives me the vertices of the simplices which partition my original simplex into finer ...
- 173
1
vote
0
answers
517
views
Solving 3D equation system (inverse-projecting a triangle)
Please, how is the equation system below named exactly (to search further literature)?
Does it have an analytical solution? If it doesn't, then what could be the fastest numerical method for it (...
- 11.6k
4
votes
1
answer
2k
views
Homogeneous system of polynomial equations
Hi all,
Previously I asked a question that currently has no satisfactory answer Least sum squares given constraints on subcomponents
It comes from an engineering problem. I was thinking to formulate ...
CommunityBot
- 1
1
vote
0
answers
185
views
Compute generalized pentagram map
Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...
- 11
5
votes
5
answers
1k
views
Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid
A friend asked me to post the following question. He's not an MO user and felt it would be better received if asked by someone who was already known to the community. This is not my area, but I'll do ...
- 30.3k
0
votes
0
answers
512
views
Orientation predicate CG
Shewchuk 97 gives me the orientation of 4 points, by finding the sign of a determinant, where the matrix is composed of the coordinates of the points. So, the signed volume of a tetrahedron, or which ...
CommunityBot
- 1
4
votes
2
answers
1k
views
Area ratio of a minimum bounding rectangle of a convex polygon
Take a convex polygon $P$ in the plane, and find its minimum area bounding rectangle, $R$. I'm interested in the ratio of the area of $R$ to the area of $P$. The ratio has a minimum of $1$ for ...
- 96.4k
12
votes
3
answers
801
views
finding the most-isolated point in a high-dimensional cube
I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find
$\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} \|\...
- 151k
3
votes
1
answer
2k
views
practical algorithm for constrained triangulation in two dimensions?
I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained ...
- 131
0
votes
1
answer
141
views
Known graph/surface invariants that can be extracted from homology over different fields
The $Z_2$-homology of a surface viewed as a simplicial complex allows us to extract interesting invariants from the resulting homology groups. $\beta_0$ is the number of connected components, $\beta_1$...
- 34.7k
10
votes
3
answers
756
views
Degree of generators of irreducible components
Let $V$ be a Zariski-closed subset of $\mathbb{A}^n_k$, where $k$ is an algebraically closed field. Assume that $V$ may be defined by polynomials of degree at most $d$ (or to put it otherwise $V$ is ...
- 27k
1
vote
1
answer
573
views
'Reference' request: Program to work with cyclic quotient singularities.
I'm looking for program code to deal with cyclic quotient singularities on normal surfaces. In particular, at the moment I need that given a singularity $p$ like $p=\frac{1}{n}(1,a)$ the code computes:...
- 3,625
4
votes
2
answers
1k
views
Area of a Convex Polygon (Described via Half-Planes)
The intersection of a collection of half-planes describes a convex polygon, whose vertices can be constructed in $O(n \log n)$ time using a divide-and-conquer approach (e.g., intersect each half-plane ...
- 151k
6
votes
3
answers
289
views
Minimum separating subdivision in Plane
Hi
I was thinking about the following problem:
Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine ...
CommunityBot
- 1
1
vote
1
answer
254
views
Characteristics of locally triangle-free graph
Hi
I am given a triangulation $T $ of a set of points $S $ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T $ whose vertices are the points ...
- 239
1
vote
1
answer
272
views
Euclidean neighborhoods on Polyhedral surface
Let $(X, Vertex(X))$ be a Polyhedral surface (defined like in Polthier) , $x_0 \in X$ a vertex. Let $B_\epsilon(x_0)$ the euclidean ball centred at $x_0$ with radius $\epsilon$, $\epsilon > max ...
- 151k
1
vote
0
answers
204
views
Which rational subfields are corresponding to the two dimensional subspaces of holomorphic differentials
I implemented the algorithm that Felipe Voloch's suggested in his reply to the question:
Subfields of a function field
the algorithm is here:
Subfields of a function field
I considered the ...
CommunityBot
- 1
10
votes
1
answer
2k
views
Can taking the projective closure of an affine variety increase the degrees of its ideal generators?
Say we have some equations $f_1(x)=0, \ldots f_k(x)=0$ defining a variety $X$ in ${\mathbb C}^n$ (not necessarily a minimal number of generators, and not necessarily of minimal degree), and suppose we ...
- 11.3k
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
8
votes
2
answers
362
views
Computational methods for dealing with geometrically complicated solid boundaries in fluid-air interface problems
Hello,
I am a PhD student who does not have extensive computational experience seeking advice from those experienced with computational modelling as to which method would be most appropriate for ...
- 1,171
4
votes
1
answer
414
views
Computing places over x in F/K(x)
Let $F$ be a function field of "transcendental degree one" over its full constant field $K$. Let $x \in F \backslash K$. We know the divisor of $(x) = (x) - (1/x)$ in $K(x)$. Could you please give me ...
CommunityBot
- 1
4
votes
3
answers
919
views
Area-preserving map between rectangles and fat polygons
Are there any well-known continuous area-preserving maps between fat convex polygons and fat rectangles? Specifically, given a fat convex polygon $C$, is there a natural way to choose a fat rectangle ...
- 45k
3
votes
1
answer
760
views
Fast approximation for local Delaunay simplex?
Consider a function $f(x)$ evaluated at a set of points $x_j\in\mathcal{D}\subset\mathbb{R}^d$. I'm working on the following type of low order interpolation method. Consider the Delaunay tesselation ...
- 5,992
14
votes
2
answers
1k
views
Subfields of a function field
Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...
- 116
4
votes
2
answers
3k
views
Numerical solution for a system of multivariate polynomial equations
Hi all,
I have a system of 6th-order polynomial equations in 4 variables $q_1, q_2, q_3, q_4$ (i.e. polynomials with all the terms such as $q_1^6, q_2^6, q_2^4 q_3^2$):
$P_k(q_1, q_2, q_3, q_4) = 0$ ...
CommunityBot
- 1
8
votes
1
answer
236
views
inferring the slope of a digitized line
Given real numbers $a$ and $b$, and an integer $n \geq 2$, let $f(n,a,b)$ be the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) minus the maximum of $(nint(ja+b)-nint(ia+b)...
CommunityBot
- 1
0
votes
2
answers
2k
views
Detect if directed cycle is clockwise or counterclockwise in 3D [closed]
I need to check if cycle given by $(x_1, y_1, z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)$ is clockwise or counterclockwise. I have found this answer: Detecting whether directed cycle is clockwise or ...
CommunityBot
- 1
5
votes
1
answer
2k
views
Intersections of irreducible components
Let $V$ be an algebraic variety (not irreducible) over $\mathbb{C}$, defined by an ideal $I = \{f_1,f_2,\dots, f_n\}$. $V$ is not necessarily pure dimensional. Suppose $V = R_1\cup R_2\cup\dots\cup ...
- 20.5k
3
votes
1
answer
818
views
Algorithm for Ham Sandwich with Points
I just recently learned the Ham Sandwich Theorem in my algebraic topology class. If we take the measure to be the counting measure and let $n=2$, then the theorem tells us that given a set of black ...
- 502
3
votes
1
answer
7k
views
Detecting whether directed cycle is clockwise or counterclockwise
Given a directed cycle in the plane I need to walk it and detect whether it is clockwise or counterclockwise.
My first idea is to gather the sum of the turn angles, where a "left" turn is a negative ...
- 7,836
0
votes
1
answer
196
views
Open questions in mesh generation
A mesh is a discretization of a geometric domain. An unstructured mesh is typically a triangulation. Unstructured meshes are catching up especially in the academic community.
I'm looking for open ...
- 3,022
2
votes
2
answers
354
views
formulate edge length problem as convex optimization problem
I want to us convex optimization to describe a problem in computational geometry.
Let $E = (E_1, E_2,\ldots , E_m) $ be a sequence of line segments in the plane, where $E_1$ and $E_m$ may be points ...
- 567
1
vote
2
answers
2k
views
Regular vs. Irregular Vertices in a Mesh
Hi everybody,
Reading about Geometry Processing, I have realized that people in this area are very interested in regular vertices(degree=6) rather than irregular ones.
Can anybody give me reasons ...
- 2,401
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
6
votes
2
answers
1k
views
Light rays bouncing around inside a sphere in d-dimensions
Suppose $S=\mathbb{S}^d$ is a unit sphere in $(d-1)$ dimensional space, with $d=3$ of special interest.
The surface of $S$ is a perfect (internal) mirror.
You stand at point $x$ (not the sphere center ...
- 85.6k
5
votes
3
answers
478
views
What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?
What is the most general class of metric spaces for which the closest pair of points in any finite subset can be found in time O(n^(1+eps))? I have studied how to do this in O(n log(n)) in the plane, ...
- 4,462
5
votes
1
answer
796
views
Minimizing variance of distances between points when mean distance is fixed
In Rd, I have n > d+1 points. The mean distance between pairs of points is 1. How can I minimize the variance of the distances (equivalently, the mean squared distance)? I'm mainly interested in d &...
- 45k