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

Filter by
Sorted by
Tagged with
8
votes
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 ...
8
votes
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 ...
5
votes
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 ...
2
votes
0answers
148 views

Best known results pairwise distance computation of high-dimensional points?

Suppose we are given a family $F$ of $n$ sets of total cardinality $N$ with elements of the sets drawn from a universe $U$ of size $|U| = d$. Alternately, suppose we have $n$ points in $R^d$, or $n$ $...
6
votes
0answers
331 views

Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?

Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate ...
6
votes
1answer
364 views

Solving multiple instances of 3SUM generated from the same set

(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM) Suppose we have a list $S$ of $n$ integers. Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ ...
10
votes
2answers
232 views

Tradeoff Bounds for Halfspace Range Counting

What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff. According to Matousek's seminal 1993 ...
8
votes
1answer
484 views

Die roll problem

Edit: I think the spirit of the question was good, but it needs to be improved. The assumptions made for the coin toss made that question trivial, and the die roll is still not precisely defined ...
10
votes
3answers
2k views

Find Shortest Pairwise Distance of Points in o(n log n)?

The following exercise has been handed out to students I supervise: Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of ...
7
votes
1answer
204 views

Voronoi diagram on surface of polyhedron

Does anyone know of work on computing the Voronoi diagram of a set of points on a polyhedron, where distance is measured by shortest paths on the surface? I am particularly interested in convex ...
6
votes
3answers
489 views

How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring ...
2
votes
2answers
417 views

NP-hard problem on planar unit disk graph

I am curious to know whether there are problems which are np-hard even on planar unit disk graphs. A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we ...
23
votes
3answers
724 views

Convex Body with minimum expected l2 norm

Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is ...
9
votes
1answer
1k views

Computing volume of high-dimensional convex polyhedra

I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-...
9
votes
1answer
656 views

Do Delaunay triangulations on the sphere maximize the minimum angle?

Delaunay triangulations in the plane maximize the minimum angle in a triangle. Does the same hold true for the Delaunay triangulation of points on the sphere ? (here the "angle" is the local angle in ...
10
votes
1answer
649 views

Voronoi diagram in a graph

Let $G$ be a graph with (positively) weighted edges. I want to define the Voronoi diagram for a set of nodes/sites $S$, to associate with a node $v \in S$ the subgraph $R(v)$ of $G$ induced by all the ...
4
votes
7answers
539 views

Menagerie of polygons

UPDATE Now community wiki. My new version of the question is: let's make a big list of classes of polygons. We may be able to produce the most comprehensive list on the web, or in the literature. ...
14
votes
3answers
389 views

Separation of a preprocessed polyhedron and a plane

I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: http://www.cs.princeton.edu/~dpd/Papers/...
0
votes
0answers
136 views

Efficiently representing sets of $n$-dimensional rectangles orthogonal an axis

Is there a data structure that allows one to represent sets of $n$ dimensional rectangles, all orthogonal or parallel to the $x$ axis. efficiently. Allowing all common set operations (union, ...
3
votes
2answers
2k views

Required mathematics for computational geometry research career

I have a computer engineering degree and i am very interested in theoretical and combinatorial aspects of computational geometry . I want to build the mathematical foundation for this area so i can ...
13
votes
2answers
413 views

Best way to determine the minimum dimension of a structure given only distances between points

I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it ...
0
votes
2answers
880 views

What is the problem in “closest pair problem” if all points share the same x-coordinate

The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large ...
8
votes
1answer
169 views

Dynamic planar exact k-nearest neighbors for pathological data

What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space: $insert(x)$ $delete(x)$ $nearest(k,x)$ (where $k$ is an ...
9
votes
2answers
2k views

Calculating the distance to the kth nearest neighbor for all points in the set

For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and ...
7
votes
2answers
214 views

Determining the convexity of a set on $S^n$

While pondering a problem on separating objects in $R^n$ by hyperplanes, I came across the following puzzle: Suppose we are given a convex subset of $S^n$ which we call $M$. For each point $p \in ...
7
votes
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 ...
10
votes
2answers
3k views

Covering a simple polygon with circles

Suppose I have a simple polygon $S$ and an integer $k$. What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$? How about if $...
17
votes
2answers
1k views

Sorting by Euclidean distance

$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$. A no-brain approach is to ...
5
votes
2answers
793 views

shortest path algorithm taking into account angular deviation

I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute betweenness centrality of road segments. At present, I am weighting the paths by metric length ...
10
votes
2answers
2k views

Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized. ...
1
vote
1answer
121 views

What methods exist for returning all points within an arbitrary closed shape?

I have been reading about range search algorithms, but most that I read apply only to a simple range (such as a standard rectangle in 2d). In a similar fashion, what options exist for range search ...
2
votes
1answer
692 views

What data structures exist for fast calculation of distances between multi-dimensional points

I'm writing a program that receives data over a network connection. Every data point is simply a 4 dimensional vertex, lets call the dimensions X,Y,Z,W. The values of each dimension are exponentially ...
4
votes
1answer
398 views

Efficiently computing the exact union of 'N' intersecting circles on a plane

I have a set of $N$ circles with a set of known radii $r_i$ on a plane of some surface area $A$. If intersection is allowed between circles, how can I most efficiently compute the exact (not ...
14
votes
2answers
585 views

The number of triangulations of a set of $n$ planar points: Why so difficult?

After hearing Emo Welzl speak on the subject this summer, I know the number of of triangulations of a set of $n$ points in the plane is somewhere between about $\Omega(8.48^n)$ and $O(30^n)$. ...
3
votes
2answers
887 views

What are some applications of computational geometry towards computer vision?

I'm interested in both of these topics independently, and wondering some good applications of comp geom within the domain of vision. What are some nice applications and potential projects of comp ...
5
votes
2answers
2k views

Computing integer points on the circumference of a given circle

Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The ...
7
votes
1answer
153 views

Dissecting tetrahedra into similar tetrahedra

(i) Does anybody know what is the smallest number $k$ such that there is a tetrahedron T that can be subdivided into $k$ tetrahedra that are similar to T ? I know $k$ is at most 8 (I know a ...
6
votes
4answers
581 views

Small $\epsilon$-nets for points and half-planes without VC dimension

I have recently learned the proof of Haussler and Welzl of the following theorem. Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ ...
13
votes
1answer
416 views

Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?

Are there any problems that are NP-complete when using Euclidean geometry but are well-defined and solvable in polynomial time for some non-euclidean geometry?
4
votes
1answer
439 views

Does kd tree requires triangular inequality for finding k-nearest neighbors

I have 3-dimensional data I want to store in a kd-tree. Additionally I have a domain-specific distance function in this space for which I have a hard time to prove the triangular inequality. Here is ...
5
votes
1answer
411 views

Place n points in a box as far away from each other as possible

Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized. In other words, I'm ...
11
votes
2answers
268 views

Art gallery variants with pairwise visibility?

The traditional art gallery problem sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region. Has anyone ...
4
votes
0answers
172 views

Implementable algorithm for Voronoi regions with obstacles

I'm looking for an algorithm that computes the Voronoi regions of a set of points contained in a polygonal region with obstacles. What would be the most simple, straightforward way to implement this? ...
13
votes
0answers
404 views

Exact nearest neighbor in $d$-dimensional Euclidean space

Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$. We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \...
19
votes
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 ...
6
votes
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 ...
1
vote
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 ...
-1
votes
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
1
vote
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 ...
2
votes
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 $...