All Questions
Tagged with computational-geometry plane-geometry
25
questions
2
votes
1
answer
190
views
Minimal degree of a polynomial such that $|p(z_1)| > |p(z_2)|, |p(z_3)|, ..., |p(z_n)|$
I was investigating the behavior of $p(x)^n \mod {q(x)}$, for some polynomials $p, q \in \mathbb{C}[x]$. We'll assume $q$ is squarefree. If $q(x) = (x - z_1) (x - z_2) (x - z_3) ... (x - z_n)$ for ...
- 3,049
2
votes
0
answers
116
views
Ellipse of least perimeter that contains a given triangle
This post is related to Smallest 3-ellipses that contain triangles and tries to clarify a basic issue.
Question: Given a general triangle T, How does one find and characterize the ellipse of least ...
- 5,827
1
vote
0
answers
38
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,206
1
vote
0
answers
121
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 ...
- 5,827
1
vote
1
answer
202
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,827
2
votes
1
answer
237
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 ...
- 5,827
3
votes
0
answers
172
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 ...
- 5,827
5
votes
1
answer
461
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 $...
- 5,827
3
votes
1
answer
181
views
On some centers of convex regions based on partitions
These questions are inspired by Yaglom and Boltyanskii's 'Convex figures'.
Winternitz Theorem: If a 2D convex figure is divided into 2 parts by a line $l$ that passes through its center of gravity, ...
- 5,827
5
votes
1
answer
153
views
On folding a polygonal sheet
Consider a polygonal sheet $P$ of area $A$ with $N$ vertices (it material is not stretchable or tearable). Let $n$ be a positive integer >=2.
Question: Let $P$ lie on a flat plane. We need to fold ...
- 5,827
0
votes
1
answer
1k
views
Fast way to generate random points in 2D according to a density function
I'm looking for a fast way to generate random points in 2D according to a given 2D density function.
For instance something like this:
Right now I'm using a modified version of "Poisson disc&...
- 121
1
vote
0
answers
27
views
Complexity of tour-expansion heuristic for the planar Euclidean TSP
This is a followup question to this one: Computational Geometric Aspects of Greedy Tour Expansion.
Assume that the candidate point, whose insertion into current incurs the least tour-length increase, ...
- 12.8k
4
votes
2
answers
212
views
Algorithm for reporting all triangles with unique interior point
What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
- 12.8k
2
votes
1
answer
485
views
Partitioning polygons into acute isosceles triangles
Question: Given an $N$-vertex polygon (not necessarily convex). It is to be cut into the least number of acute isosceles triangles.
Based on this MathSE discussion, one can think of a method to get $\...
- 5,827
7
votes
1
answer
730
views
To minimize the Hausdorff distance between convex polygonal regions
Definition: The Hausdorff distance is the greatest of all the distances from a point in one set to the closest point in the other set.
Question: Given two convex polygonal regions P1 and P2 on the ...
- 5,827