# Tagged Questions

The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves ...

73 views

### What series of 'hyperpolyhedrons' do exist? Is there an effective way to derive their cross-sections by 3-d subspace?

There are two obvious series of 'hyperpolyhedrons'. 'Hyperoctahedron' with vertices $(\pm1,0...0), (0,\pm1,0,...0)...(0,...0,\pm1)$ and each vertex connected by an edge with each other vertex ...
165 views

### filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular sub-...
477 views

### Algorithm to find the point in a convex polygon closest to an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$? A linear algorithm of course works, computing the ...
2k views

### Star-Shaped polygons

We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon. The art-gallery ...
302 views

### Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
358 views

### Delaunay-like algorithm to get four sided polygons instead of triangles?

Is there an algorithm similar to the Delaunay triangulation which can organize a set of points into a set of four sided polygons instead of triangles?
56 views

### Reconstruct polyhedron from sections

There is a convex polyhedron $P \subset \mathbb{R}^{3}$ and there are its planar sections $S_{1}, \ldots, S_{n}$ througth planes $\pi_{1}, \ldots, \pi_{n}$, $S_{i} \subset \pi_{i}$. All these $S_{i}$ ...
603 views

### Segment Tree vs Interval Tree

Segment trees and interval trees both answer stabbing queries about line segments. In 1D, they both take $O(n \log{n})$ preprocessing time and $O(\log{n} + A)$ query time where n is the number of line ...
3k views

### Given a tetrahedron, how to find the outward surface normals for each side?

Say I have a triangle in $3$D space. I can get the surface normal by calculating the vector cross product of two of the edges. But, lets say I make this a tetrahedron. How can I work out the outward ...
356 views

### How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm?

Note: I'm a programmer, not a mathematician - please be gentle. I'm not even really sure how to tag this question; feel free to re-tag as appropriate. I'm using the Douglas-Peucker algorithm to ...
118 views

### Good data structure for hyperbolic tiling

Say you're doing something computational where each data point is a tile in a (not necessarily Euclidean) 2-dimensional tiling, for instance, a Life-like cellular automata. You might want a data ...
130 views

1k views

### Finding the major and minor axis vertices for an ellipse given two conjugate diameters?

I've been googling, searching forums and looking in my old algebra/trig books to try to understand how to find the end points to the major and minor axis of an ellipse given the end points of two ...