2
votes
0answers
67 views

Generalization of notion convexity

I am searching for the correct term (if exists) for the following Set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists arc of radius $r$ ...
4
votes
1answer
370 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
517 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 ...
1
vote
2answers
217 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
192 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
265 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
474 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 ...
2
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
430 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
411 views

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

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
561 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
809 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
756 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
438 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
302 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 ...
3
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
527 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
754 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 ...