Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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. ...
Nandakumar R's user avatar
  • 5,979
20 votes
2 answers
25k views

Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible. I know almost nothing about this subject, so I've been searching on Google ...
user14059's user avatar
  • 201
14 votes
2 answers
540 views

Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?

Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties: $M(a,a)=a\qquad$ (identity) $M(a,b)=M(b,a)\qquad$ (commutativity). and possibly $M(M(a,b),M(a,c))=...
Yaakov Baruch's user avatar
11 votes
2 answers
3k views

Algorithm for embedding a graph with metric constraints

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
Matthew Kahle's user avatar
6 votes
1 answer
2k views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or math.stackexchange. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
fajrian's user avatar
  • 163
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
3 votes
0 answers
141 views

Optimal intersections between planar convex regions

Here is an earlier discussion that could be related: On comparing planar convex regions of equal perimeter and area We are broadly interested in placing two given planar convex regions so that the ...
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
17 votes
2 answers
2k views

Efficiently determine if convex hull contains the unit ball

Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
Simd's user avatar
  • 3,377
16 votes
2 answers
5k views

Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
Joord Jacobsen's user avatar
12 votes
2 answers
11k views

Covering a polygon with rectangles

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
10 votes
0 answers
441 views

A new $\ell_p$-metric on the hyperspace of finite sets?

Let $(X,d)$ be a metric space and $Fin(X)$ be the family of all non-empty finite subsets of $X$. For every $n\in\mathbb N$ the elements of the power $X^n$ are thought as functions $f:n\to X$ where $n:=...
Taras Banakh's user avatar
  • 41.9k
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
8 votes
2 answers
339 views

Angle subtended by the shortest segment that bisects the area of a convex polygon

Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
Tom Solberg's user avatar
7 votes
2 answers
1k views

Is a given point in the interior of the convex hull of a given finite collection of points?

Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
Igor Rivin's user avatar
  • 96.4k
7 votes
1 answer
3k views

Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?

Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points. The $LEC$ problem is stated in this way: find a $LEC$ whose ...
Alessandro Jacopson's user avatar
6 votes
1 answer
761 views

Checking if one polytope is contained in another

I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other. At the moment I am ...
bandini's user avatar
  • 491
6 votes
0 answers
219 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 ...
Nandakumar R's user avatar
  • 5,979
6 votes
5 answers
4k views

Formulas for equidistant curves

I'm trying to draw on the computer a curve that keeps always the same distance(given as parameter) from a given curve. I know the formula for the given curve. I tried moving perpendicular to the first ...
Iulian Serbanoiu's user avatar
6 votes
2 answers
189 views

Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon

For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π. Given a convex polygon, how does one algorithmically find the point (...
Nandakumar R's user avatar
  • 5,979
5 votes
4 answers
540 views

How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights. Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ...
TerronaBell's user avatar
  • 3,059
5 votes
0 answers
309 views

Upper bounds on art gallery problems using independent witnesses

Given a polygon $P$, the art gallery problem looks to find a smallest set of points that sees all of $P$. One way of bounding the number of guards necessary (from below) is to find a largest set of ...
Michael Biro's user avatar
  • 1,182
5 votes
2 answers
294 views

Convex caps with prescribed edges

Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
Mohammad Ghomi's user avatar
5 votes
0 answers
213 views

Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
user avatar
4 votes
2 answers
2k views

Breaking a rectangle into smaller rectangles with small diagonals

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
Tom Solberg's user avatar
  • 4,049
2 votes
1 answer
84 views

'Constrained morphing' of planar convex regions

Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints. Qn: If $C_1$ and $...
Nandakumar R's user avatar
  • 5,979
2 votes
1 answer
116 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 ...
Nandakumar R's user avatar
  • 5,979
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
0 votes
0 answers
93 views

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, will the least area convex m-gon Q that contains P be such that an edge of Q coincides with an edge of P (in other words Q cannot be such that P ...
Nandakumar R's user avatar
  • 5,979
0 votes
0 answers
42 views

Construct pairs of $n$-dimensional convex bodies with given ratios ($p$) of volumes

Given a dimension $n$ and a number $p \in (0,1)$, to what extent is it possible (in what cases) to construct a convex set $A$--not a hypersphere--and a "snugly" inscribed (InscribedFigure) ...
Paul B. Slater's user avatar