# Tagged Questions

**4**

votes

**1**answer

500 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

**2**answers

871 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

**2**answers

236 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

**0**answers

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

**1**answer

321 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

**2**answers

553 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

**1**answer

4k 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

**2**answers

439 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

**1**answer

416 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

**1**answer

581 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

**1**answer

822 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

**4**answers

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

**2**answers

772 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

**2**answers

452 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

**1**answer

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 ...

**4**

votes

**2**answers

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 ...