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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ (...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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|...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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:...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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/...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 894

1
2 3 4 5
9