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
1
answer
520
views
computing the boundary of a union of polytopes
Let $P_1,\dots ,P_m\subset \mathbb{R}^n$ be $m<\infty$ convex polytopes in $\mathbb{R}^n$, and $U:=\bigcup_{j} P_j$ their set-theoretic union. What algorithms are known for computing the boundary $\...
- 14k
1
vote
1
answer
208
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 ...
- 5,979
1
vote
2
answers
680
views
Regular paths along surface of sphere
I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$.
The movement should be repetitive, so that ...
- 133
1
vote
1
answer
3k
views
Covering an arbitrary polygon with minimum number of squares
I have a problem whereby, given an arbitrary polygon with any number of points, I need to cover the whole area by a number of fixed size squares. I can easily find a set of squares which covers the ...
- 51
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 ...
- 111
1
vote
2
answers
124
views
Are there variants of Euclidean Steiner Tree problem that are known to be in P?
Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have ...
- 5,979
1
vote
1
answer
73
views
Partitioning polygons into obtuse isosceles triangles
Ref:
Partitioning polygons into acute isosceles triangles
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
https://math.stackexchange.com/questions/1052063/...
- 5,979
1
vote
1
answer
144
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.
...
- 5,979
1
vote
1
answer
253
views
whatever happened to the conference International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)?
I am not sure of a better place to ask this, hopefully someone here knows something...
I've been "away" from computational geometry topics for a bit and thought I'd catch up in some way by checking ...
- 121
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)=...
user33954
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:...
- 2,215
1
vote
1
answer
103
views
Algorithm to find largest planar section of a convex polyhedral solid
We add a bit more on shadows and planar sections following On a pair of solids with both corresponding maximal planar sections and shadows having equal area . We consider only polyhedrons.
Given a ...
- 5,979
1
vote
1
answer
134
views
An algorithm to arrange max number of copies of a polygon around and touching another polygon
A related post: To place copies of a planar convex region such that number of 'contacts' among them is maximized
Basic question: Given two convex polygonal regions P and Q, to arrange the max ...
- 5,979
1
vote
1
answer
61
views
On largest convex m-gons contained in a given convex n-gon where m < n
This post is the inside-out variant of 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, how to find the max area convex m-gon Q ...
- 5,979
1
vote
1
answer
591
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
1
vote
1
answer
138
views
Packing L's in Tans and L's in L's
I'm a young researcher and I'm pretty new in this field. I want to work on packing problem "L's in Tans" and "L's in L's" as presented on https://erich-friedman.github.io/packing ....
- 121
1
vote
1
answer
464
views
Relation between variables (vertexes, edges, regions and faces) in three dimensional Voronoi diagram
A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D. In two dimensions, any Voronoi diagram has vertexes(V), edges(E) and regions(F) that equal ...
- 19
1
vote
2
answers
269
views
Convergence of an iterated sequence
Let $K=[0,1]^2$ be a square and $p\in (0,1)$ be a fixed number. We define a map $F: K^2\to K^2$ as follows.
For $(x_1,y_1), (x_2,y_2)\in K$, it follows by a straightforward computation that there ...
- 345
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
1
vote
1
answer
85
views
Smoothly deforming a set of three-dimensional points
I want to deform a 3D mesh according to 3 or more control points, meaning that the transformation is constituted by pre-images $c_i$ and images $c_i'$ of these control points. Each point of the mesh ...
- 111
1
vote
1
answer
178
views
Inside-out dissections of solids -2
We record some general questions based on
Inside-out dissections of solids
Inside-out dissections of a cube
Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
- 5,979
1
vote
1
answer
104
views
Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon
This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
Given a convex n-gon, ...
- 5,979
1
vote
1
answer
68
views
To maximize the volume of the polyhedron resulting from perimeter-halvings of a convex polygonal region
We add one more bit to Forming paper bags that can 'trap' 3D regions of max surface area (note: some possibly open related questions are also in the comments following the answer to above ...
- 5,979
1
vote
1
answer
78
views
To optimally wrap convex laminae with paper
Ref: On folding a polygonal sheet, Multi-layered wrapping of polyhedra
Basic intent: to wrap a given convex planar lamina with a convex sheet of non-stretchable paper (such that every point on both ...
- 5,979
1
vote
1
answer
127
views
Smallest trapeziums containing a given convex n-gon
Question: Given a planar convex $n$-gon $C$, to find the smallest area / smallest perimeter trapezium (trapezoid) - a convex quadrilateral with at least one pair of mutually parallel edges - that ...
- 5,979
1
vote
1
answer
51
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
1
vote
1
answer
160
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
1
vote
1
answer
1k
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
1
vote
1
answer
99
views
Estimating volume of a simple object
Volume computation is $\#P$ hard.
Take the $[0,1]^n$ polytope.
Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves.
Volume of bigger section is $\...
- 13.9k
1
vote
1
answer
130
views
Computational Geometric Aspects of Greedy Tour Expansion
Has the following problem already been investigated from the Computational Geometry point of view and what are the results regarding worst case complexity?
Given
a finite set $\mathcal{P}...
- 13.2k
1
vote
1
answer
146
views
Omitting constraints of polynomial system
Let $n_1, n_2 \geq 1$ be known integer constants.
Suppose that we have the following system of $n$ polynomial inequalities
for which we know that there exists a feasible solution $(p_1, p_2) \in (0,1)...
- 175
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 ...
1
vote
1
answer
226
views
Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier
Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...
- 851
1
vote
1
answer
98
views
Inferring the properties of a visibility blocker tangential to a point-like light source
Imagine there's a point-like particle undergoing radioactive decay at some position $(0,0,0)$ in Euclidean $3$-space. We encapsulate this particle with a spherical detector for the decay products it ...
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
2
answers
407
views
Which data structure should I use for hierarchical T-meshes and PHT-splines?
Recently, I'm working on something about polynomial splines over hierarchical T-meshes, which is basically a rectangular grid that allows T-junctions. I want to do some numerical experiments but I don'...
- 163
1
vote
0
answers
68
views
To partition a triangle into $n$ convex pieces with sum of number of sides over all pieces maximized
This post is a variant on To cut a triangle into $n$ $p$-sided polygonal regions.
Question: Given a positive integer $n$, a triangular region is to be cut into $n$ convex pieces so that the sum over ...
- 5,979
1
vote
0
answers
37
views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function
$$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$
Can we find all the ...
- 11
1
vote
0
answers
58
views
On partitioning the surface of a convex solid into geodesically convex equal area regions
We refer to a subset S of the surface of a convex solid C as geodesically convex if the shortest path along the surface of C joining any two points in S lies entirely within S (and if there are more ...
- 5,979
1
vote
0
answers
13
views
Complexity of counting maximal points in query orthogonal rectangles
The problem stated in the title is the following: given an $n\times n$ binary matrix $M=\left(m_{rc}\right)$ report the number of $1$'s in a query rectangle
$[i,j]\times[h,k]$
$1\le i\lt j\le n,\, 1\...
- 13.2k
1
vote
0
answers
22
views
Calculating an optimal scaling factor for Delaunay triangulations
consider a finite set $\mathcal{P}(x,y)=\lbrace(x_1,y_1),\dots,\,(x_n,y_n)\rbrace$ of points in the Euclidean plane and let $\mathrm{DT}(x,y)$ be the Delaunay triangulation of $\mathcal{P}(x,y)$
...
- 13.2k
1
vote
0
answers
142
views
Explicit computation of Čech-cohomology of coherent sheaves on $\mathbb{P}^n_A$
$\newcommand{\proj}[1]{\operatorname{proj}(#1)}
\newcommand{\PSP}{\mathbb{P}}$These days I noticed the following result of (constructive) commutative algebra, which I think is probably well known ...
- 708
1
vote
0
answers
93
views
Inside-out dissections of a cube
Ref:
Inside-out polygonal dissections
Inside-out dissections of solids
Definitions: A polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 5,979
1
vote
0
answers
96
views
An algorithm to decide whether a convex polygon can be cut into 2 mutually congruent pieces
This post is based on the answer to this question: A claim on partitioning a convex planar region into congruent pieces
A perfect congruent partition of a planar region is a partition of it with no ...
- 5,979
1
vote
0
answers
65
views
Algorithm to generate configurations with kissing number 12
That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...
- 111
1
vote
0
answers
91
views
A claim on the largest area circular segment that can be drawn inside a planar convex region
This post adds a little to To find the longest circular arc that can lie inside a given convex polygon
A circular segment is formed by a chord of a circle and the line segment connecting its endpoints....
- 5,979
1
vote
0
answers
91
views
Dissection of polygons into triangles with least number of intermediate pieces
This wiki article: https://en.wikipedia.org/wiki/Wallace%E2%80%93Bolyai%E2%80%93Gerwien_theorem shows the dissection of a square into a triangle via 4 intermediate pieces. It appears easy to form a ...
- 5,979
1
vote
0
answers
41
views
Are there rectangles that can be cut into non-right triangles that are pair-wise similar and pair-wise non-congruent?
We generalize the questions of Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
Can any rectangle be cut into some finite number of triangles that ...
- 5,979
1
vote
0
answers
92
views
Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces
A (non square) rectangle can obviously ...
- 5,979
1
vote
0
answers
89
views
Bounds for minimax facility location in a convex region
An earlier question: Facility location on manifolds
A possibly related earlier post: Cutting convex regions into equal diameter and equal least width pieces - 2
The minimax facility location problem ...
- 5,979