Tagged Questions

1answer
445 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 ...
1answer
62 views

Covering the annulus of d-cube

Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C+x$ = {$~\lambda c+x|c\in C$} for some $x\in R^d$ is called homothetic copy of $C$. The number ...
0answers
36 views

Covering the annulus of symmetric convex body

Consider a symmetric convex body $A$ in $R^d$. Now, we draw another object, $A'$, concentric and translated with respect to A and having radius slightly greater than twice to the radius of $A$. Now ...
1answer
288 views

Biggest ball included in an intersection of balls

I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i)$ and $\forall i, r_i \geq 1$, there exists a ...
1answer
78 views

Inferring the properties of a visibility blocker tangential to a point-like light source

Imagine there's a point-like particle undergoing radioactive decay at some position $(0,0,0)$ in Euclidean $3$-space. We encapsulate this particle with a spherical detector for the decay products it ...
0answers
94 views

Boundary surfaces in a 3d Voronoi tessellation with obstacles

Let $x_1,\dots,x_n$ be a set of points in $\mathbb{R}^3$ and let $\mathcal{O}_1 ,\dots, \mathcal{O}_m$ denote a set of polyhedral obstacles. What is the name for the surfaces that describe the ...
1answer
44 views

Uniformly sampling the solution space for points where the free termini of two rays, anchored at 3-space points, can intersect

I have two rays, one of length $L_1$ and one of length $L_2$. I anchor these rays, each at one end, on the 3-space points $p_1$ and $p_2$. Assuming that the Euclidean distance between $p_1$ and ...
1answer
185 views

What properties does generalized Delaunay triangulation have?

Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
1answer
830 views

Subtract Rectangle from Polygon

I'm looking for an algorithm that will subtract a rectangle from a simple, concave polygon and return a remainder of polygons. If the rectangle encloses the polygon, the remainder is null. In most ...
5answers
504 views

Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

A friend asked me to post the following question. He's not an MO user and felt it would be better received if asked by someone who was already known to the community. This is not my area, but I'll do ...
1answer
2k views

Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
2answers
2k views

Covering a Polygon with Rectangles

I am tyring to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
1answer
206 views

Checking if one polytope is contained in another

Hi, I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other. At the moment I am ...
2answers
451 views

Area ratio of a minimum bounding rectangle of a convex polygon

Take a convex polygon $P$ in the plane, and find its minimum area bounding rectangle, $R$. I'm interested in the ratio of the area of $R$ to the area of $P$. The ratio has a minimum of $1$ for ...
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 ...
1answer
297 views

Pointers/Papers on subdivision of planar quadrilateral meshes (PQ-Mesh) in 3D?

I'm interested in the subdivision of planar quadrilateral meshes (PQ-Meshes). Meshes consisting only of planar quadrilaterals, like discrete Voss surfaces and alike. I've been searching the web for ...
2answers
756 views

The straightest possible path embeddable in a path of polygons

I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below. Initially my interest was limited to ...
4answers
645 views

Algorithm for k-medians in a convex polygon

Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon? That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a ...
0answers
101 views

Queries On PH Quintic Splines

This is with respect to the Pythagorean Hodograph Splines of degree 5, developed here: link text. I'm trying to code these up and can't really get clear about a couple of points: (1) Are these ...
1answer
1k views

What can be said about the Shadow hull and the Sight hull?

This is a question implicitly raised by Is the sphere the only surface all of whose projections are circles? Or: Can we deduce a spherical Earth by observing that its shadows on the Moon are always ...
2answers
797 views

Light rays bouncing around inside a sphere in d-dimensions

Suppose $S=\mathbb{S}^d$ is a unit sphere in $(d-1)$ dimensional space, with $d=3$ of special interest. The surface of $S$ is a perfect (internal) mirror. You stand at point $x$ (not the sphere center ...
2answers
1k views

Computational geometry, tetrahedron signed volume

Short version: I'm trying to compute the orientation of a triangle on a plane, formed by the intersection of 3 edges, without explicitly computing the intersection points. Long version: I need to ...
1answer
574 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 ...