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.
404
questions
0
votes
1
answer
83
views
Reference request: How to construct a diffeomorphism between point clouds
I'm interested in the following question:
Given two sets $S = \{x_1, ..., x_N\}$ and $T = \{y_1, ..., y_N\}$ each consisting of $N$ distinct points in $\mathbb{R}^n$, how can we construct a ...
- 449
2
votes
0
answers
40
views
Cylinder orientation representation
I'm trying to find an efficient computation and representation for the following problem.
Given a cylinder with height $h$ and radius $r$ with a given position $\mathbf{x} = [x, y, z]$ and $N$ number ...
- 21
1
vote
0
answers
28
views
Fermat point amidst polygonal obstacles
Consider $k$ distinct points in 2D-plane with $n$ convex polygonal obstacles. Is there a poly-time algorithm (poly in $k$ and the total number of obstacle vertices) to find a point outside of all ...
- 1,126
3
votes
0
answers
171
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,096
1
vote
0
answers
35
views
Are cells of 4-polytopes a convex polyhedron by definition?
I'm going by the Wikipedia definition for a 4-polytope.
Do by definition, cells of 4-polytopes have to be a convex polyhedra?
If not, then are there polyhedra with non-convex faces?
If yes, is it the ...
- 11
7
votes
1
answer
211
views
Finding maximal prefix of a simple curve
Let $S$ be a piecewise-linear simple curve. For a point $p_1$ on $S$ I want to determine a maximal interval $I$ on $S$ starting in $p_1$ such that $I$ is contained in a unit disk. Is this possible, or ...
- 73
3
votes
0
answers
89
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
2
votes
1
answer
44
views
Optimal unions of planar convex regions
This post continues Optimal intersections between planar convex regions.
Question: Given two planar convex polygonal regions $C_1$ and $C_2$, how does one algorithmically find how to place and orient ...
- 3,451
1
vote
0
answers
45
views
Angles between edges of a geometric graph and graph invariants
Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph?
I'm interested to see what else is ...
- 466
0
votes
0
answers
23
views
How to do an elevated 2D Delaunay triangulation?
This is what I call an elevated Delaunay triangulation:
This is also called a 2.5D Delaunay triangulation.
To do it, I simply perform an ordinary 2D Delaunay triangulation with the (x,y)-coordinates, ...
- 2,053
1
vote
0
answers
38
views
Comparing convex planar regions of equal perimeter and area - 2
We try to extend On comparing planar convex regions of equal perimeter and area .
Given two planar convex regions C1 and C2 both with unit perimeter, we define the difference between C1 and C2 as the ...
- 3,451
2
votes
0
answers
138
views
Reduced Voronoi diagram
I am currently reading Differentiable Surface Triangulation presented at Siggraph Asia 2021.
I think most of the paper is clear to me, though I keep re-reading through to see if I miss details.
The ...
0
votes
1
answer
114
views
A variation on the projective Nullstellensatz
Let $V$ be a $\mathbb{C}$-vector space, and let $f_1,\dots,f_n \in S^d(V^*)$ be homogeneous polynomials of degree $d$ for which $V(f_1,\dots, f_n)=\{0\}$.
Must there exist a positive integer $k\geq d$ ...
- 894
2
votes
1
answer
31
views
Minimal vertices 3D polygon fitting between inner and outer boundaries
I have a set of 3D points representing a convex hull which I define as the inner boundary. The points are then offset outwards by a selected distance (the 'error') and I define this expanded hull as ...
- 21
3
votes
2
answers
145
views
Finding a point inside a surface
I have a triangulation of a surface without boundary in $\mathbb{R}^3$.
The triangulation gives a unit normal pointing outwards for each triangle. I need to find some point in the interior of the ...
- 33
14
votes
1
answer
308
views
Are hyperbolic $n$-manifolds recursively enumerable?
Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?
Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit ...
- 3,172
3
votes
0
answers
115
views
Optimal intersections between planar convex regions
We are broadly interested in placing two given planar convex regions so that the intersection has maximal area or perimeter. One could use translations, rotations and reflections(flipping over) of ...
- 3,451
2
votes
1
answer
103
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
- 5,708
0
votes
0
answers
64
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....
- 3,451
3
votes
1
answer
103
views
Finding the smallest centrally symmetric region that contains a convex planar region
Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C?
Note 1: In question ...
- 3,451
1
vote
0
answers
68
views
A ratio to measure 'roundedness' of planar convex regions
Ref: A center of convex planar regions based on chords
The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
- 3,451
3
votes
2
answers
86
views
Partition of polygons into 'congruent sets of polygons'
Definition: Two finite sets of polygons $A$ and $B$ are congruent if we can match polygons in $A$ in a one-one manner with polygons in $B$ with each matched pair of polygons mutually congruent.
...
- 3,451
1
vote
0
answers
28
views
On partitioning n-gons into pieces with reflection symmetry
Is 3(n-2) a tight lower bound on the least number of reflection symmetric pieces that any general n-gon can be cut into? What if we consider only convex n-gons?
A kite is a reflection symmetric ...
- 3,451
5
votes
2
answers
190
views
On intersections of several convex regions
Question: Given n convex planar regions. Required to place them (in suitable position and orientation) so that that part of the plane lying under all the regions (their common intersection) is of ...
- 3,451
3
votes
2
answers
127
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|...
- 51
3
votes
0
answers
44
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 $...
- 2,921
1
vote
0
answers
97
views
A center of convex planar regions based on chords
This is based on Chapter 6 of 'Convex figures' by Yaglom and Boltyanskii. This post also continues On two centers of convex regions.
A point $P$ in the interior of a planar convex region $C$ divides ...
- 3,451
1
vote
0
answers
31
views
Multi-layered wrapping of polyhedra
This post continues from How big a box can you wrap with a given polygon? and Convex polyhedra that can be folded from convex polygons. One can also mention 'k-fold coverings of the plane' as examined ...
- 3,451
2
votes
1
answer
89
views
Convex polyhedra that can be folded from convex polygons
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf.
Therein is stated the theorem: Every convex polygon folds to an infinite number (a continuum) of noncongruent ...
- 3,451
6
votes
0
answers
200
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 ...
- 3,451
2
votes
0
answers
89
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 ...
- 3,451
1
vote
0
answers
49
views
Further queries on inside-out polygonal dissections
The following is based on Inside-out polygonal dissections
Definition: We say that a polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 3,451
1
vote
1
answer
113
views
On a possible variant of Monsky's theorem
See Wikipedia for Monsky's theorem which states: it is not possible to dissect a square into an odd number of triangles all of equal area.
Questions: Are there quadrilaterals that allow partition into ...
- 3,451
1
vote
0
answers
78
views
On vertices on convex smooth closed surfaces
Question: Given a smooth, convex, closed surface. How would one find points on it with the property: the average of the geodesic distances from that point to all other points on the surface (the ...
- 3,451
1
vote
1
answer
44
views
On triangulations and "coverage" of circumcircles
Let $P$ be a convex quadrilateral defined by four vertices $a$, $b$, $c$, and $d$. Suppose that the circumcircle of $\triangle abd$ contains $c$.* Let $D(\triangle abc)$ to denote the area enclosed by ...
- 173
2
votes
1
answer
87
views
Triangulations of point sets — obtuse and acute triangles
Given a planar configuration of points in general position. It is known that the Delaunay triangulation is the 'fattest' triangulation possible. It is also easily seen that given 7 points with 6 of ...
- 3,451
1
vote
1
answer
122
views
Line segment-triangle intersection algorithm [closed]
currently in my project I'm using signed tetrahedron volume to check whether a line segment intersects a triangle. Initially I've found this approach in the great answer provided by professor O'Rourke:...
- 11
3
votes
0
answers
134
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 ...
- 3,451
15
votes
1
answer
575
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 173
1
vote
1
answer
133
views
On convex polygons contained in convex polygons
In what follows '$n$-gon' stands for '$n$-vertex polygonal region'.
Question: Given a convex $n$-gon $C$, find the smallest convex region $R$ such that $C$ is the smallest $n$-gon that contains it.
...
- 3,451
1
vote
0
answers
45
views
Deployment and dispersion in triangular regions
Definitions (from C. Stanley Ogilvy's 'Tomorrow's Math'):
Deployment: To place a specified number $n$ of points (stations) in a region such that the maximum distance of any point in the region from ...
- 3,451
5
votes
1
answer
243
views
Check if a polygon has an axis of symmetry in $O(n)$ time
Question: Is it possible to check if an $n$-gon has an axis of symmetry in $O(n)$ time?
Note: An $O(n^2)$ algorithm is easy to see: it is easy to check if any given line is an axis of symmetry of the $...
- 3,451
1
vote
1
answer
86
views
Total area of cuboids projected on plane
Lets define n arbitrarily scaled, rotated, located cuboids, and plane by normalized direction vector.
Cuboids is supposed to be "flattened" by orthogonal projection on the plane, so we can ...
- 11
3
votes
1
answer
220
views
Computing intersections of unit disks
Given $n \geq 2$ points in the plane, how can one efficiently (or even inefficiently!) compute the number of corner-points belonging to the boundary of the intersection of the unit disks centered on ...
- 17.3k
2
votes
0
answers
120
views
Random sets of points and hyperplanes in high dimensions
We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \in\mathbb{R}^d$ selected uniformly at random from the unit origin-centered ball $\mathcal{B}^{d}$.
Consider the random ...
- 1,173
1
vote
1
answer
367
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
6
votes
0
answers
135
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 ...
- 3,451
8
votes
1
answer
530
views
Final project ideas - computational geometry
Next semester I am teaching (the programming part) of a course in Computational Geometry. There are 14 weeks of class, two "pure theory/blackboard" hours per week, one "theory/...
- 319
0
votes
0
answers
40
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 ...
- 11.1k
1
vote
0
answers
137
views
Using Bertini software to determine whether or not a variety is empty
I have a system of polynomials $f_1,\dots, f_n \in \mathbb{C}[x_1,\dots, x_m]$, and I would like to determine whether the set of solutions to the system $f_1(x)=\dots=f_n(x)=0$ is empty or not. Since ...
- 894