Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
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 ...
user avatar
  • 3,912
1 vote
1 answer
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 ...
user avatar
  • 157
2 votes
1 answer
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 ...
user avatar
  • 3,912
5 votes
2 answers
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 ...
user avatar
  • 83
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
84 views

Where to find this unpublished Bentley's research paper?

Bentley, J.L. [1977]: Solution to Klee's rectangle problems, unpublished manuscript, Dept. of Computer Science, Carnegie-Mellon University, 1977. Is it classified or not archived at all?
user avatar
  • 151
2 votes
2 answers
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 ...
user avatar
  • 3,912
0 votes
1 answer
24 views

Getting a "sub-polytope" of a concave d-dimensional polytope, given some one dimensional inequality

The question will be hard to understand without an example, so let's given an example first: Let's say I have a 2 dimensional concave polytope, defined by a circular sequence of its vertices: $(0,0), (...
user avatar
0 votes
0 answers
10 views

Applying Divergence to Kinetic Data Structure

Problem statement :- There is a moving source($s$) and other moving points ($p_{1}.... p_{n}$). There are fixed obstacles and a fixed destination point($d$). In each time step I have to query "Is ...
user avatar
  • 157
1 vote
1 answer
40 views

How can I implement this algorithm to find all pairs of points at a distance of 1?

I am trying to find an algorithm which, given a set of N points on a 2D plane, can find all pairs of points at a distance of exactly 1. I believe this is similar to this question. I looked at the ...
user avatar
2 votes
1 answer
33 views

finding a hemisphere that contains all points of a given set S

Let $S$ be a finite set of points on the unit sphere $\mathbb{S}^2$. My question would be: is there an easy way to either find a great circle $C$ such that all points in $S$ are inside one of the ...
user avatar
1 vote
0 answers
100 views

A total order of rectangles related to containment

Suppose you have a set of rectangles $R_1,\dots,R_n$ in the plane, each described by an upper left point $p_1 \in \mathbb R^2$ and a lower right point $p_2 \in \mathbb R^2$, all pairwise different. ...
user avatar
0 votes
0 answers
61 views

How we can solve two lines of this algorithm in $o(n^2)$?

Given $n=2k$ pairs of points $P=\{(p_1,q_1),(p_2,q_2),\dots,(p_k,q_k)\}$ in the plane. Also, let $d(.)$ return distance between two points. Now, our goal is to act as bellow: For each $(p_i,q_i)$ ...
user avatar
  • 1
0 votes
0 answers
22 views

Intersecting multiple rays with a polytope

I have multiple rays of the form: \begin{align} x_1 &= c_1 \\ x_2 &= c_2 \\ &\dots \\ x_d &= c_d \\ \end{align} And need to find all intersection points between each ...
user avatar
1 vote
0 answers
27 views

Finding intersections between given equations and d-dimensional polytope

I am currently storing a $d$-dimensional polytope as a list of $d$-dimensional points. In order to implement an algorithm, I need to find intersections between my polytope and $d$ equations, of the ...
user avatar
0 votes
0 answers
27 views

What are the real-world applications of the Minimum Bottleneck Spanning Tree?

I'm currently writing my Research Plan for a post-graduate application (MS level) in the field of Computational Geometry. So I'm looking into tackling the Euclidean Minimum Bottleneck Spanning Tree ...
user avatar
  • 123
1 vote
2 answers
135 views

Sorting segments from high to low

I have a set of segments. None of them intersect or touch each other, and none of them have slope $0$ or infinity (i.e. the endpoints have different $x$ and $y$). All segments have length $> 0$. ...
user avatar
0 votes
1 answer
31 views

Find the lowest line given the same x-axis

There are a bunch of lines in the 2D Plane. Is there an efficient algorithm to find the line that has the lowest y value given the same x? Thank you! Could we also generate a list of ranges, where for ...
user avatar
2 votes
1 answer
57 views

Research project problem on Computational Geometry

(Most fair region) Let $P$ be a set of $n$ points in the two-dimensional plane. Each point in $P$ is either colored red or blue. Given an axis-aligned rectangle $R_{ab}$ of size $a\times b$ , design ...
user avatar
1 vote
0 answers
16 views

Distance between two points on 3D Triangular Mesh Manifold

I'm working on my bachelor thesis (on Computer Science) and right now I'm having a problem about finding shortest path between two points on 3D triangular mesh that is manifold. I already read about ...
user avatar
3 votes
1 answer
92 views

finding an algorithm for creating a priority search tree in linear time with presorting

A priority search tree is a binary tree satisfying the following: every node $u$ stores a point $p_u = (x_u,y_u)$ every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate. If $...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
2 votes
1 answer
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)...
user avatar
  • 69
4 votes
0 answers
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 ...
user avatar
  • 1
2 votes
1 answer
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 ...
user avatar
  • 1
2 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 157
0 votes
0 answers
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 ...
user avatar
  • 157
1 vote
0 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
  • 69
1 vote
0 answers
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 ...
user avatar
  • 11
2 votes
1 answer
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,...
user avatar
  • 123
2 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 1
3 votes
1 answer
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 ...
user avatar
  • 1
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 111
3 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 159
4 votes
2 answers
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. ...
user avatar
2 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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, ...
user avatar
  • 13
6 votes
2 answers
248 views

What edges are not in a Gabriel graph, yet in a Delauney graph?

It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{...
user avatar
  • 123
0 votes
0 answers
16 views

Why are point clouds useful for large datasets of geometries?

In my computer graphics course I came across this "pro" for point clouds: Useful for large datasets (>> 1 point / pixel) I'm trying to wrap my head about it, I know drawing is ...
user avatar
  • 101
1 vote
0 answers
33 views

Data structure for quickly obtaining all axis-aligned rectangles completely within rectangular region

I'm stuck on a homework assignment. There are $n$ axis aligned rectangles and we need to find a data structure of size $O(n \log^2 n)$ and query time $O(\log^3 n + k)$ that can give all rectangles ...
user avatar
  • 11
1 vote
1 answer
48 views

Kinetic Data Structure

Currently i am studying Kinetic Data Structure thesis by Julian Basch. I am feeling stuck in some points. Are there any other resources to understand it properly ?? Edit:- I am very new to this data ...
user avatar
  • 123
1 vote
0 answers
30 views

Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
user avatar
  • 193

1
2 3 4 5
16