# Questions tagged [cg.comp-geom]

Computational Geometry is the study of geometric problems from a computational perspective. Examples of problems include: computation of geometric objects such as convex hulls, dimensionality reduction, shortest path problems in metric spaces, or finding a small subset of points that approximates some measure of the whole set (i.e. a coreset).

267 questions
Filter by
Sorted by
Tagged with
72 views

### Term for a correspondence of two point sets regarding their ordering in each dimension

Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of ...
417 views

### comparing polyhedra (or even more specifically convex hulls) in d dimensions

Does anybody have information on whether the problem of determining whether 2 polyhedra in d dimensions are the same, is polynomial or NP-complete, if so? Thanks
467 views

### How to efficiently compute a bounding box of a 2D compact function support?

I've come to an interesting problem. Let's have a 2D scalar function F and make some assumptions on it: it has compact support (region where it is defined and non-zero) its support consists of at ...
150 views

3k views

### The quad-edge data structure (Delaunay/Voronoi)

2 questions for the computational geometers or algebraists: I am just beginning to dive into computational geometry and I am loving it =) I am attempting to read the famous article by Guibas and ...
331 views

### Find optimal room from which to visit all other rooms in a rectangular floorplan

Suppose we have an orthogonal polygon with holes (all walls are axis-parallel). All vertices can be on integer coordinates, if that helps. Partition the polygon into rectangular rooms. I would like ...
345 views

### Covering a set of intervals, continued

Peter Taylor and Tsuyoshi Ito solved a previous question that I posted: Covering a set of intervals I have a slight variation on that question that I'd also like to ask. I'm not sure what the ...
558 views

### Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results. Specifically, I'm interested in seeing some hardness proofs for problems that are ...
276 views

### Partitioning a connected shape into rectangles

I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers ...
228 views

### What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)

This is a cross-post from MathOverflow. The problem of testing whether a simplicial face lattice (informally, a poset of faces) is polytopal is sometimes called the Steinitz Problem. Sturmfels and ...
399 views

### Find all nearby points in a set, for each element of the set

Given a finite set $S$ of points in $\mathbb R^p$ and a number $\rho$, my collaborators and I want to find, for each $s\in S$, the other points in $S$ that are within $\rho$ of $s$. Of course there's ...
903 views

### Covering a set of intervals

(I was redirected from mathoverflow in asking this) Hello, I'm trying to determine if the following problem is solvable in polynomial time: given a collection of $n$ half-open intervals $[s_i, t_i)$ ...
2k views

### Algorithms for Polygon triangulation

I had hard time finding algorithm or published papers on Self intersecting polygon(also polygon with hole structure) triangulation. Can any one guide me to find published paper/algorithm, please? PS:...
1k views

### Complexity of computing shortest paths in the plane with polygonal obstacles

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
551 views

### Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that ...
685 views

### Is that particular case of the "minimum weight solution to linear equations" still NP-complete?

We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find ...
510 views

### Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
2k views

### Sorting array of distances by proximity to each other

I was playing with geolocation on maps and stumbled on an interesting problem: I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes ...
140 views

### Process on finite points in a line

This is related to some old posts that were closed because someone had felt that they're related to homework. All I'm looking for here is a reference to a paper that may have partially or completely ...
191 views

### Geometric differencing

The diff procedure can be generalized to operate on objects other than strings. For instance, I imagine that computational geometry asks questions like: "Given two volumes, and allowed only the ...
480 views

### Finding the largest set of points of limited diameter

Given points $p_1,\ldots,p_n$ in $\mathbb{R}^{d}$ and a distance $l$ find the largest subset of these points such that the Euclidian distance of no two of them exceeds $l$. What is the complexity of ...