# Questions tagged [computational-geometry]

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

787 questions
Filter by
Sorted by
Tagged with
35 views

### Alternative parameterizations of the circle

When solving numerical problems with circles, one often has to sample these at numerous points, not necessarily in a uniform way. Evaluating the $(\cos\theta,\sin\theta)$ values can represent a ...
1 vote
37 views

### A nearest neighbor data structure for meshes

I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
28 views

### Delaunay triangulation from an EMST

Assume you know the Euclidean Minimum Spanning Tree of a set of $n$ 2D points (in general position). Is there an efficient way (faster than $O(n \log n)$ operations) to obtain the Delaunay ...
93 views

### The optimal complexity of intersecting a line with a convex hull of a set of points in 2d

The problem: in 2d, given a line and an unordered set of $N$ points with real coordinates, find the intersection between the line and the convex hull of the points. Clearly, one can explicitly ...
28 views

### Finding smallest triangle to fit all points

I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given ...
10 views

### Approach for flattening a 3-d cube given cuts

Take a cube. Cut seven of its edges. Consider a graph whose vertices are the centers of the faces of the cube. If two faces share a common edge, then the graph also has an edge connecting the two ...
1 vote
84 views

### Where to find this unpublished Bentley's research paper?

Bentley, J.L. : Solution to Klee's rectangle problems, unpublished manuscript, Dept. of Computer Science, Carnegie-Mellon University, 1977. Is it classified or not archived at all?
43 views

### Nearest line-segment to a query point or conversely

I have a set of line segments (say 1000 of them) and a query point. I want to find the segment which is the closest in the Euclidean sense (if the point does not project on the segment I accept two ...
24 views

46 views

### Checking whether a set of points in the plane can be bi-partitioned with a certain diameter

I am working on a problem in geometry and I encounter the following problem. Suppose given $n=2k$ points $P$ in the plane. And we want partition points into two group Is there an algorithm that ...
44 views

### Lower bound for querying KD tree

In the book Computational Geometry, Algorithms and Applications there is an exercise asking: In the proof of the query time of the kd-tree we found the following recurrence:  Q(n)= \begin{cases}O(1)...
146 views

### Find a dynamic programming solution that minimize the sum of the diameters of two clusters?

I asked a question at this link, where I suggested a greedy algorithm for this problem: Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
79 views

### Does this greedy algorithm minimize the sum of the diameters of two clusters?

Suppose given $2n$ points in the plane and we want to partition points into two clusters $C_1$ , $C_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the ...
36 views

### Maximum Intersection of Convex Partitions

Given a bounded, convex polytope $C \subset R^d$, I have $n$ partitions of the polytope $C$ into at most $m$ smaller polytopes (disjoint on all but sets of measure zero). These smaller polytopes have ...
1 vote
45 views

### Prove an edge that minimizes the Euclidean distance crossing a cut is in the Delaunay triangulation

Let $P$ and $Q$ be two disjoint point sets in the plane. (Think of them as a red point set and a black point set.) Let $p \in P$ and $q \in Q$ be two points from these sets that minimize the Euclidean ...
28 views

### How to find the second most closest pair of points modifying the Divide and Conquer?

I know the Divide and conquer approach for the finding the closest pair of points and the proof of correctness. Can we modify it in such a way so that , we can find the 2nd most closest pair. I am ...
1 vote
30 views

### Membership Oracle (MO) for $K+\epsilon B$ given MO for $K$

Let $K$ be a convex compact set in $\mathbb{R}^d$. Suppose that a Membership Oracle $\mathcal{M}_{K}$ for the set $K$ is available; given a point $x\in \mathbb{R}^d$, the Oracle returns 0 if $x$ is in ...
1 vote
67 views

### Computing convex hull by triangle point inclusion

In my computational geometry book they present the following $O(n^4)$ algorithm for computing the convex hull of a pointset $P \subset \mathbb{R}^2$ assuming general position on the points in $P$: For ...
1 vote
47 views

### Data Structure for finding all bounding boxes that overlap or are contained in a given bounding box

I am looking for a data structure that needs to have very fast and accurate queries to solve the following: The input: A set of 3 Dimensional axis-aligned bounding boxes B A separate 3D axis aligned ...
20 views

### What is the counterclockwise index of diagonal endpoints in a diagonal$\to$triangulation algorithm?

I'm reading the book Computational Geometry in C by O'Rourke. One of the problems ask the following Diagonals$\rightarrow$triangulation. Given a list of diagonals of a polygon forming a triangulation,...
21 views

### Pairwise intersections of segments in a rectangle

Let V be a set of vertical segments, and H be a set of segments parallel to a line (e.g. a line with slope -1). We want to find a data structure for set S = V ∪ H to find all pairs (v,h) of segments ...
127 views

### Prove that the set of edges of a Delaunay triangulation of $P$ contains an EMST (Euclidean minimum spanning tree) for $P$

I was studying computational geometry on my own from "Computational Geometry: Algorithms and Applications" - by Mark de Berg. In chapter 9, i.e. Delaunay Triangulation, there is an exercise ...
1 vote
36 views

### Point location in axis parallel rectangles

I'm new in computational geometry and I have the following question: Suppose Given $n$ disjoint axis parallel rectangles $R$ in plane. We want preprocess $R$ in $O(n\log n)$ with $O(n)$ space such ...
89 views

### Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles

Suppose a convex polygon $P$ in plane is given. We want to triangulate it such that any arbitrary line $L$ intersects with $O(\log n)$ triangles. I divide $P$ in half using a diagonal line. Then I ...
1 vote
50 views

### crossings of edges of a geometric graph

I am considering geometric graphs $G=(V,E)$ where $V$ is a set of points in $\mathbb{R}^2$ and the edges are straight line segments between vertices. See the image: Now I want to calculate all pairs ...
98 views

### Diameter of a convex hull

I've been looking at algorithms for finding the diameter of a convex polygon, and while I like the Shamos' algorithm using antipodal points which is general and applicable to various other problems, I ...
154 views

### Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
1 vote
44 views

### find 3 points among some given 2D points such that the triangle includes another given point

Ideally, these would be the points that form the smallest (nondegenerate or degenerate) triangle. However, I can admit a large amount of approximation to get it to a lower order of complexity. I can ...
91 views

### Given a vector of points, what is the fastest algorithm to find all pairs of points at a distance of 1?

Given a vector of points (on the 2D plane), what is the fastest algorithm to find all pairs of points at a distance of 1? Of course, I could use the $O(N^2)$ algorithm to check all pairs of points. ...
67 views

### Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$

The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...
95 views

### Find a bipartition of points using blackbox

Suppose given $n$ pair of points $P=\{(p_1,q_1),\dots,(p_n,q_n)\}$ in the plane that each pair $(p_i,q_i)\in \mathbb{R}^2$ can't belong to the same group. We want to partition points into $K$ groups ... 1 vote
60 views

### Find all integer points that lay in a 3-ball with a given radius

How can I efficiently find all lattice points in the cubic lattice $Z^3$ (that is to say, all integer points in a 3-space) that lay in a closed ball of radius $R$ centred at the origin? Essentially, ...
248 views

1 vote