1
vote
0answers
17 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
0
votes
1answer
15 views

How to reduce 3 dimensional optimization to 2 dimensions?

I am trying to minimize the surface area of a parallelepiped of unit volume. Using Volume = xyz(1 + 2cos(a)cos(b)cos(c) - cos^2(a) - cos^2(b) - cos^2(c))^1/2 = 1 where x,y,z are edge lengths and ...
0
votes
0answers
25 views

How to find the parallelepiped of unit volume with minimal surface area?

Is it best to approach this problem using edge lengths and the angles between them? I am trying to reduce the problem to two dimensions, although I haven't successfully done so yet So I have Volume ...
1
vote
1answer
59 views

Why geometric median cannot be solved analytically

$\DeclareMathOperator*{\argmin}{argmin}$ For a given set of $m$ points $x_1,...,x_m$ with each $x_i\in \mathbb{R}^n$, the geometric median (or the weber point) is defined as $$\argmin\limits_{y \in ...
0
votes
0answers
37 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
3
votes
0answers
57 views

What is the 'optimal' equal-area partition of a circle?

What is the (an?) n-partition of a circle that meets the following criteria: The boundaries of each partition can be represented as a union of finitely many finite-piecewise-smooth simple closed ...
1
vote
1answer
34 views

Bounding volume of catmull-rom splines

I need to compute a 2D "spherical" bounding volume for the part of a catmull-rom spline $S(t)$ with four control points $P1$, $P2$, $P3$ and $P4$ in the domain $0 \le t \le1$. The purpose is to reduce ...
0
votes
0answers
36 views

Farthest vector direction relative to other vectors

I wished to know the cheapest computational means (be it analytical or numerical) to find the vector from origin (normalised or not; I do not care about its magnitude) given any arbitrary set of ...
0
votes
0answers
19 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
1
vote
1answer
102 views

The minimum number of circles in order to obtain a COVER of a specific square

Suppose a unit square $X$, with side length $l=1$ as below, which is COVERed by a set $Y$ of circles with the same constant radius of $r=\dfrac{\sqrt{2}}{10}$, where a ...
0
votes
2answers
50 views

Maximum Area of a Triangle when 1 Side, Perimeter Known

This is an example of a "quantitative comparison" question the GRE would test. Suppose the following information is known: one side of a triangle has length 12 the perimeter of the triangle is 40 ...
0
votes
1answer
20 views

Steepest descent direction with surface constraint (geometry problem)

Let say I have a function $f(x,y,z)$, defined on a surface by the level curve $g(x,y,z)=c$. I want to know what is the direction of the steepest descent at a given point, taking into account the ...
2
votes
2answers
52 views

Find an equation for a moving rod

The two endpoints of a 1-metre long rod have an initial position at $(0,0),(0,1).$ The rod slides continuously to the position $(1,0),(0,0)$ sweeping out a region in the positive quadrant. Determine ...
1
vote
1answer
26 views

Maximum area ellipse that does not include a set of points

I'm interested in finding the maximum area ellipse that does not cover some points $\mathbf{p}_i$ and that is centered at the origin. Hence, ideally I'd like to solve this optimization problem: $$ ...
1
vote
0answers
54 views

A point minimizing total great circle distance to a given set of points on a hemisphere

If you have a set of points on a hemisphere, how do you find a point on that hemisphere that has the minimum total great circle distance to the points in the set.
3
votes
2answers
48 views

Largest Equilateral Triangle in a Polygon

Is there an algorithm to determine the largest equilateral triangle in a convex polygon?
0
votes
1answer
30 views

Minimal volume of a tetrahedral

I'm unsure how to solve the following problem: Let $\textbf{p}=(a,b,c) \in \mathbb{R}^{3}$ with $a,b,c > 0$. For $\alpha , \beta > 0$ the equation $$\alpha (x-a)+ \beta(y-b) + (z-c) =0$$ ...
0
votes
1answer
28 views

What is $s$ in s-energy (eg. Riesz s-energy)

I'm trying to understand fekete problems. There is a variable $s$ and a related concept of 's-energy' [1] [2] [3] [4] that comes up repeatedly when borrowing the concept of potential energy to find ...
3
votes
1answer
28 views

Find a maximum triangle that lies on a polyline (with constraints)

If there's a polyline (a GPS track, actually) with a lot of points (could be several thousand), that looks like this 1) How can I find such a triangle with the biggest possible perimeter, that its ...
0
votes
1answer
22 views

Convex hulls for a finite amount of points

I'm trying to understand what a convex hull intuitively is, and say given for a set of points $(x,y)\in\mathbb{R}^2$ how is it generated from these points? I tried reading the wikipedia article and ...
16
votes
4answers
491 views

How fat is a triangle?

The slimness factor of a geometric shape in 2 dimensions is the ratio between the side-length of its smallest containing square and its largest contained square. This is an important factor in ...
9
votes
1answer
178 views

Characterization of sphere.

I'm editing the question because I think the previous formulation was leaving a key element of the problem out and that was making it impossible to answer the question. I tried to update/improve the ...
4
votes
1answer
76 views

Division of plane into equal area regions

We divide a plane ($\mathbb{R}^2$) into infinite number of regions each of area equal $1$. We can use only (one-dimensional) curves which may meet at points. Fix a point $p$ on a plane and consider ...
0
votes
0answers
17 views

Solve for transform of rotating frame to fixed frame given points in rotating frame and a planar constraint

Say there are 2 coordinate systems, with one orbiting around the other. Call one fixed ƒ and the other rotating ρ. The goal is to find the transform between the two frames. What's known is A set of ...
0
votes
0answers
20 views

How to find iso function value points without exploring all points in 2D space

Consider a 2D graph with dim1 and dim2 represented as X and Y respectively. The range of X and Y are 1 to 100. Hence there are 10000 points in the 2D space. Each point in the space is some function of ...
0
votes
1answer
92 views

finding points with maximum distance between them on a circle

I'm a computer science student working on a problem in computer graphics and looking for a formula that can find the x and y positions of a set of N points on the surface of a circle so that the ...
1
vote
1answer
140 views

Find the ellipse inscribed in a triangle having the maximum area

If we have a triangle of sides $a,b,c$, there are infinite ellipsis inscribed in the triangle. How can I find that having the maximum area? Is this ellipse the circle, or in what cases the maximum ...
5
votes
2answers
241 views

Maximal area covered by two triangles in unit circle

What is the maximal area covered by two triangles in a unit circle? There are no restrictions other than that. They can overlap, touch the circle, not touch the circle etc. So far I have shown In ...
0
votes
0answers
31 views

Dual of a polyhedra vs. dual of an optimalization problem

There are lot of fields where the term duality appear. Is there any relationship between dual of an optimalization problem and dual of a polyhedra?
0
votes
0answers
57 views

Maximizing $x\left(\displaystyle\sum_{k=0}^n \sqrt{1-kx^2}\right)$

Here's the motivation for my problem: Consider a right-angled triangle with legs of length 1 and $x$ and on the leg of length 1, and construct another right-angled triangle whose hypotenuse is 1 ...
4
votes
1answer
101 views

10 points inside a square - minimum distance between any of them

A square of side 1 is given, and 10 points are inside the square. If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose ...
6
votes
1answer
83 views

Platonic solids and charged particles

It is known that there are five Platonic solids: If, lets say, there are 4 particles with the same electricity charge and whose movement is constrained to be on a sphere, resulting forces will ...
7
votes
2answers
132 views

Prove That the Second Moment is Minimized with a Circle Packing

Graham and Sloane studied the problem of minimzing the second moment of disks on the plane, i.e. minimize $$ U = \frac{1}{d^2} \sum_{i=1}^{n} || \mathbf{p}_i - \bar{\mathbf{p}} ||^2 $$ s.t. ...
0
votes
2answers
156 views

Optimization of the surface area of a open rectangular box to find the cost of materials

A rectangular storage container with an open top is to have a volume of 10 cubic meters. The length of the box is twice its width. Material for the base costs ten dollars per square meter and for the ...
1
vote
2answers
75 views

Maximize the distance between a point and a bounding rectangle

There are $n$ random points in the $x-y$ plane, whose coordinates are known beforehand. We can use a minimum bounding rectangle (MBR) to bound these points. In this scenario, the MBR can be rotated, ...
3
votes
0answers
53 views

How to find the minimal path between points in a planar set with holes in it?

When I was a commuter student, I would park in a very large parking that that had a set of stairs in a corner that I had to climb. In general, I had to park far away from this corner in an almost full ...
0
votes
0answers
56 views

max and min values on symmetric polytope

Let $-N\leq t \leq N$. Let $A$ be regular $(N-1)$-dimensional simplex with vertices $(t,0, \ldots, 0)\ldots (0, 0,\ldots, t)$ and $B$ be regular $(N-1)$-dimensional simplex with vertices $(t-N+1,1, ...
2
votes
1answer
105 views

How to calculate the point on the sphere that is nearest to some given points on the sphere?

Given some points $X=\{x_i:||x_i||=1,i=1,\ldots,n\} $ located on the sphere, how to calculate the point $\tilde{x}$ on the sphere that is nearest to these given points. That is to say ...
3
votes
1answer
179 views

Finding the shortest path length on a curved surface(hyperboloid)

I wish to find the minimum path length between two points $P_1(\sqrt2,0,-1)$ and $P_2(0,\sqrt2,1)$ on a hyperbolic surface $S =\{(x,y,z)\in R^3\ |\ x^2+y^2-z^2=1\}$ I faintly recall studying ...
2
votes
1answer
145 views

Minimum distance to points in plane

Someone told me that the the following problem is elementary. Given three points $a=(-5,0)$, $b=(0,5)$ and $c=(5,0)$ in $\mathbb R^2$ with Euclidean norm: $$\mbox{minimize}\;\; \; f(x)=\|x-a\| + ...
2
votes
1answer
38 views

Chord Maximisation

I am currently going back through all the "Challenge" questions in preparation for exams, and for this I do not know where or how to start, any hints would be appreciated. Now the way I have ...
2
votes
2answers
209 views

Closest distance between two quadratic curves

I'm having trouble with the following problem : "find the closest distance between $x^2+4y^2=4$ and $xy=4$" I tried to solve using the properties of ellipse and hyperbola, but the relatively tilted ...
1
vote
0answers
30 views

Finding coordinates of nodes in a graph

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other ...
0
votes
0answers
108 views

Maximum area of quadrilateral of given perimeter.

Let $0\lt a\lt b$ (i) Show that among the triangles with base $a$ and perimeter $a + b$, the maximum area is obtained when the other two sides have equal length $b/2$. (ii) Using the ...
17
votes
3answers
310 views

What is the largest circle that fits in $\sin(x)?$

Imagine dropping a circle into the trough of $\sin(x)$. Would it reach the bottom or get wedged between two points on the curve? Depends on the size of the circle. So, what is the radius of the ...
0
votes
1answer
40 views

$|\langle a_i, a_j\rangle|$ for $p$ points on a unit circle.

Is it true that given any $p$ points $a_1, .., a_p$ on a unit [euclidean] circle, there is always a pair $i \ne j$ such that $|\langle a_i, a_j\rangle| \ge \cos{\pi/p}$?
0
votes
0answers
17 views

Dimension of face of a polytope in terms of linear functionals

A face of a polytope is a subset consisting of the points for which some linear functional is maximized. Can one determine the dimension of the face in terms of the linear functionals which are ...
0
votes
1answer
38 views

Highest Volume/Area Ratio

Given a fixed volume of a solid, what would be the shape of such solid that would minimize the its surface area? How to determine it? I thought about it, but I cannot find an algorithm that doesn't ...
2
votes
3answers
82 views

Find out minimize volume (V) of tetrahedral

I have this problem: On space $ (Oxyz)$ given point $M(1,2,3)$. Plane ($\alpha$) contain point $M$ and ($\alpha$) cross $Ox$ at $A(a,0,0)$; $Oy$ at $B(0,b,0)$; $C(0,0,c)$. Where a,b,c>0 Write the ...
1
vote
1answer
17 views

Placing a shape on a grid

I am interested in a certain kind of geometrical optimisation problems. I will illustrate it on a semi-concrete example: You are given a two-dimensional shape, say a polygon, and a rectangular ...