# Tagged Questions

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 ...
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 ...
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?
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 ...
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. ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
1k views

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