4
votes
1answer
480 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 ...
1
vote
2answers
805 views

Trilateration problem

When trying to develop an algorithm for a program, I got with the following problem: Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...
0
votes
2answers
232 views

Enlcosing a set of ellipses within one ellipse

Hello, Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?
5
votes
0answers
198 views

Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
4
votes
1answer
314 views

Polyline Averaging

I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them. The input lines do not loop. ...
5
votes
2answers
540 views

Finding the convex combination of vertices which yields an inner point of a polytope

Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of ...
4
votes
1answer
3k 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 ...
2
votes
2answers
438 views

Where to submit a new convex hull algorithm

Hi, Recently I am working on a new convex hull algorithm. I would like to know if there is any forum where I can submit my work.
0
votes
1answer
415 views

How to formulate such problem mathematicaly? (line continuation search) [closed]

I have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to some ...
4
votes
1answer
576 views

Finding integer points on an N-d convex hull

Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is ...
2
votes
1answer
821 views

Algorithm for the shortest edge-disjoint path between all the points of a 2D cloud

Hi all! I have an array of points with their coordinates X and Y. Each point represents a bus stop. I need to sort the points in a sequence by giving them sequence numbers, so that the path from the ...
1
vote
4answers
1k views

Finding the union of N random circles arbitrarily (or conspiratorially) placed on a two-dimensional surface

Please consider a two-dimensional surface populated with a set of Cartesian coordinates $(x_i, y_i)$ for $N$ circles with individual radii $r_i$, where $r_{min} < r_i < r_{max}$. Here, the ...
1
vote
2answers
768 views

Calculating the surface area distribution of two-dimensional projections for a polytope

My question concerns the existence of a nice (deterministic?) method/algorithm for calculating the distribution of surface areas for two-dimensional projections of an arbitrary polytope (or convex ...
9
votes
2answers
451 views

When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?

To ask this question in a (hopefully) more direct way: Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ ...
2
votes
1answer
1k views

Matrix approximation

Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where ...
5
votes
2answers
304 views

Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
4
votes
2answers
1k views

Minimum-area bounding quadrilateral algorithm

There are a few algorithms around for finding the minimal bounding rectangle (OBB) containing a given (convex) polygon. Does anybody know about an algorithm for finding a minimal-area bounding ...
7
votes
2answers
556 views

Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$ This can be done efficiently by linear programming (time polynomial in ...
5
votes
4answers
775 views

How to compute the average distance till intersection within a triangle in R^2?

Lots of simple questions because I am a noob. You are given 3 points in R^2; A, B, C forming a triangle with area > 0. You pick an arbitrary point inside ABC and an arbitrary direction. After some ...
9
votes
4answers
2k views

How Does One Find the “Loneliest Person on the Planet”?

I'm looking for the algorithm that efficiently locates the "Loneliest Person on the Planet", where "loneliest" is defined as: Maximum minimum distance to another person -- that is, the person for ...