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
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 ...
- 601
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
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$ ...
- 101
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
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
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 ...
user30211
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
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
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
0
votes
0
answers
95
views
Boolean operation on n dimensional polyhedron
A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
- 21
0
votes
0
answers
54
views
Attached convex "hulls"
Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
- 13.2k
0
votes
0
answers
42
views
Construct pairs of $n$-dimensional convex bodies with given ratios ($p$) of volumes
Given a dimension $n$ and a number $p \in (0,1)$, to what extent is it possible (in what cases) to construct a convex set $A$--not a hypersphere--and a "snugly" inscribed (InscribedFigure) ...
- 723
0
votes
0
answers
37
views
Restrictions on crossing edges in Delaunay triangulations
what can be said about crossing edges in Delaunay triangulations, i.e. about pairs of edges that constitute to the heaviest perfect matching int the $K_4$ induced by the quadruplet of adjacent ...
- 13.2k
0
votes
0
answers
89
views
Why there isn't lexicographically smallest solution to a bounded linear program?
I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
- 1
0
votes
0
answers
76
views
Minimum-cost vertex transformations to achieve a planar graph embedding
Consider an undirected planar graph $G = (V,E)$ (not necessarily simply connected) whose current embedding in the plane has edge intersections.
Consider algorithms in which vertexes $v_i$ can be ...
- 2,558
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 ...
user76479
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 ...
- 109
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
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 ...
- 143