# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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$ (...
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 ...
1 vote
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 ...
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, ...
1 vote
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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....
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 ...
1 vote
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 ...
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. ...
1 vote
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 ...
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 ...
127 views

1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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:...
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 ...
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 ...
1 vote
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. ...
1 vote
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 ...