Skip to main content

All Questions

Filter by
Sorted by
Tagged with
4 votes
1 answer
356 views

Left and right halves of convex curve

Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even. A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
Xd00fg's user avatar
  • 214
2 votes
1 answer
194 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 ...
Daniel Weber's user avatar
  • 3,319
2 votes
0 answers
119 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 ...
Nandakumar R's user avatar
  • 5,979
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 ...
DSM's user avatar
  • 1,216
1 vote
0 answers
124 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 ...
Nandakumar R's user avatar
  • 5,979
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 ...
Nandakumar R's user avatar
  • 5,979
2 votes
1 answer
272 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 ...
Nandakumar R's user avatar
  • 5,979
3 votes
0 answers
175 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 ...
Nandakumar R's user avatar
  • 5,979
5 votes
1 answer
491 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 $...
Nandakumar R's user avatar
  • 5,979
3 votes
1 answer
190 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, ...
Nandakumar R's user avatar
  • 5,979
5 votes
1 answer
156 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 ...
Nandakumar R's user avatar
  • 5,979
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&...
shoosh's user avatar
  • 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, ...
Manfred Weis's user avatar
  • 13.2k
4 votes
2 answers
213 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, ...
Manfred Weis's user avatar
  • 13.2k
2 votes
1 answer
504 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 $\...
Nandakumar R's user avatar
  • 5,979
7 votes
1 answer
768 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 ...
Nandakumar R's user avatar
  • 5,979
6 votes
1 answer
143 views

Minimizing the number of segments in drawings of planar graphs

Every planar graph has at most $3n-6$ edges, where $n$ is the number of vertices. Moreover, every planar graph can be drawn with straight-line edges in the plane, without crossings. For example, for ...
Lviv Scottish Book's user avatar
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}...
Manfred Weis's user avatar
  • 13.2k
2 votes
1 answer
69 views

Maximal opening angle of a polygon from a point [closed]

I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point. One ...
shoosh's user avatar
  • 121
2 votes
0 answers
126 views

Intersecting balls with convex regions and a bisector thereof

This question is related to my previous posting Angle subtended by the shortest segment that bisects the area of a convex polygon Let $C$ be a convex region in the plane and let $s$ be the shortest ...
Tom Solberg's user avatar
0 votes
2 answers
3k views

Determine the boundary points of a set of points [closed]

I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$? There are methods like convex hull, concave hull and $\...
janak's user avatar
  • 17
1 vote
0 answers
66 views

Non-Convex Polygons with "Antipodal Visibility"

by "antipodal visibility" of planar, simple polygons I mean the following property: if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal length,...
Manfred Weis's user avatar
  • 13.2k
8 votes
2 answers
752 views

Are point sets of the same order type connected by continuous (order type)-preserving motion?

Given two general position point sets in $\mathbb{R}^2$ of the same size and order type, is it possible to continuously move the points of one set until they coincide with those of the other set in ...
Nima Hoda's user avatar
3 votes
2 answers
1k views

maximum number of shortest path among a set of n triangle obstacles

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...
user23354's user avatar
9 votes
5 answers
13k views

Get a point inside a polygon

I have a 2D polygon of arbitrary geometry. I need to find any point that is inside of that polygon. Taking the center won't work, because the polygon might not be convex. Is there a way to quickly ...
user10306's user avatar
  • 201
3 votes
3 answers
2k views

Is there a simple criterion to determine if two parallelograms intersect?

Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty? Note that I do not need to actually find the intersection.
Philipp's user avatar
  • 979