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

263 questions
Filter by
Sorted by
Tagged with
0answers
109 views

### Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D

This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes: Is there an algorithm that enumerates the ...
2answers
281 views

### Is the cutting lemma true with O(r) lines?

The cutting lemma (a.k.a. cell decomposition lemma) states that given $n$ lines in the plane it is possible to divide it into $O(r^2)$ regions (even triangles) for any $1\le r\le n$ such that the ...
3answers
377 views

### What defines a “decent” polygon?

Acknowledgments/apologies (Feb 10). Thanks to those who have taken the time of reading this question and trying to find an answer (I've upvoted the three answers so far). I hope that after some ...
0answers
148 views

1answer
459 views

### Minimum BoundingBox on n-dimensional case

I need to develop an algorithm to define the minimum bounding box on an N-dimensional space. http://en.wikipedia.org/wiki/Minimum_bounding_box Every reference to this problem that I'm able to find ...
2answers
3k views

2answers
1k views

### A data structure for minimum dot product queries

Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
2answers
573 views

### Incremental drawing of large graphs

I have the following problem: I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs ...
1answer
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 ...
1answer
408 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
0answers
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 ...
1answer
149 views

### List the $k$-faces of an $n$-dimensional simplex

Suppose you are given an $n$-dimensional simplex S = [ 0 1 ... n ] which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given \$...