Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
9 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 ...
0
votes
0answers
19 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 ...
2
votes
1answer
88 views
+50

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
1answer
40 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 ...
3
votes
2answers
66 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. ...
2
votes
0answers
53 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 ...
0
votes
0answers
92 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
1answer
41 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, ...
6
votes
2answers
232 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{...
0
votes
0answers
14 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 ...
1
vote
0answers
26 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 ...
0
votes
0answers
16 views

Object Visibility Graphs

I have gone through this defination A graph G = (V, E) is called an object visibility graph if there is a set of non- intersecting objects so that there is a one-to-one correspondence between the sets ...
1
vote
1answer
41 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 ...
1
vote
0answers
26 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 ...
0
votes
0answers
28 views

Closest pairs of points with conquer without divide approach

In an algorithm where I have to search for the pair of points in a plain, with the smallest distance: suppose that we want to use a "Divide and Conquer" approach. Is it possible to make it ...
0
votes
0answers
53 views

Compute intersection points of n circles

Let $S$ be a set of $n$ circles in the plane. I need to describe a algorithm which computes all the intersection points of the circles. The algorithm should run in $O((n + k)\log n)$ time, where $k$ ...
1
vote
1answer
31 views

How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
1
vote
1answer
32 views

Efficient Way To Compute Points Where Convolution Equals Zero

I want to model the following procedure. Given a shape $L\subseteq\mathbf{R}^2$ (imagine e.g. a letter) and another (could be convex if it makes life easier) shape $K\subseteq\mathbf{R}^2$, I want ...
1
vote
0answers
22 views

When Triangulating monotone polygons, how can diagonals be added to a DCEL in constant time?

I am working on the polygon triangulation algorithms from "Computational Geometry - Algorithms and applications 3rd ed", chapter 4. I've managed to turn polygons into y-monotone polygons ...
1
vote
1answer
22 views

Efficient intersection detection between disks with identical radius

I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose ...
2
votes
1answer
23 views

Deploying circles on 2D space to cover most of points

My question is related to this one Minimize number of circles to cover set of points In a 2D space, I have a set of points. I can deploy up to $k$ circles with radius $r$ to the space, and my goal is ...
0
votes
1answer
48 views

Compare growth rate two functions

Suppose $f_1(n)=n\log^*n$,$f_2(n)=n\log h$ that $h$ is number of vertices of convex hull. Can we conclude that $$f_1+f_2=O(f_2)?$$ Edited: Note that, $h$ is a function accroding to $n$ that $h\leq n$, ...
2
votes
0answers
46 views

fast intersection-test for great circle arcs (intersecion of geodesics on the sphere)

I have the following problem: let $(a_1,b_1)$ and ($a_2,b_2)$ be to geodesic lines on the sphere, i.e. great circle arcs. I need to determine, if the two arcs intersect. I already have a working ...
0
votes
0answers
25 views

Understanding the L1 metric (rectilinear) spanning tree algorithm

I am required to find a rectilinear (manhattan) spanning tree in O(n log n), where n is the number of vertices to connect. There is an algorithm for this described at topcoder. My issue is that I have ...
3
votes
1answer
55 views

Algorithm to find the shortest path and its length for moving between many geometries

I have a set of 2D geometric figures in Cartesian space, as shown in the image. Each geometric figure has a start point and an end point (among other characteristics). For closed geometries, such as a ...
3
votes
1answer
53 views

N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
4
votes
1answer
46 views

Find the segments set with the lowest number of 2D collisions

I am given 2 sets of n 2D Points. I need to find the segment set S where each of the n segments has its start and end in the first and second set respectively. The requirement is that each point must ...
3
votes
1answer
74 views

Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Given: a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\cdots,\vec{{V_i}_{-1}},\vec{{V_i}_0},\vec{{V_i}_1},\cdots$ ...
3
votes
0answers
31 views

Periodic 4D Triangulations

I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
4
votes
1answer
111 views

Point in Polygon on the sphere

I'm looking at geometric objects on the sphere and need to determine if a point on the sphere is inside a spherical polygon. In our case a spherical polygon is a an ordered set of vertices $v_1v_2......
1
vote
1answer
50 views

Similarity measures for (geometric) triangulations

In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a fixed pointset $S$. I would like to cluster similar triangulations. ...
4
votes
0answers
57 views

Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
2
votes
0answers
54 views

Fast algorithm to check if a query line segment contains a point that is not covered by $n$ disks in $\mathbb{R}^2$

I have a list of $n$ disks in $\mathbb{R}^2$ with center and radius $(x_i, y_i, r_i)$. I also have $Q$ line segments $l_1, l_2, ..., l_Q$. I am interested in preprocessing the $n$ disks (or the line ...
4
votes
0answers
64 views

Efficient 2d interval merging product

Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval. ...
1
vote
1answer
119 views

Is there an algorithm to solve the following point clustering problem?

According to this post Given $n$ points $P=\{p_1,p_2,\dots,p_n\}$ in 2D space, and a matrix $D^{n\times n}$ with the distances between each pair of points, we want to partition the points into two ...
7
votes
0answers
157 views

Finding a rainbow independent set in a circle

Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
2
votes
0answers
54 views

Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
2
votes
0answers
19 views

Algorithm to batch individual cells into blocks based on attribute

This is a real world algorithms problem I came across while coding an application for excel. The background: In excel, we have to write color information to the sheet one cell at a time - there are no ...
1
vote
0answers
67 views

How does Bowyer-Watson algorithm for Delaunay triangulation run in $O(n^2)$ but runs over all the simplexes?

The Bowyer-Watson algorithm for Delaunay triangulation is known to run in $O(n^2)$ according to the authors, where $n$ is the number of data points in $\mathbb R^d$. In addition, the algorithm (for ...
2
votes
0answers
27 views

Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
0
votes
1answer
37 views

Given a rectangle and a circle (having a lattice point as a center) find the number of lattice points of the rectangle inside the circle

The title explains the question easily. Also the radius of the circle is always an integer. The naive algorithm I thought was to check each and every lattice point of the rectangle but I wonder if we ...
1
vote
0answers
9 views

Methods to interpolate between 2 topologically identical 3D meshes

I have 2 3D surface meshes. These meshes have vertex-correspondence and have the same topology (same edges and triangles connecting the vertices). However, the vertex positions (3d coordinates) are ...
3
votes
0answers
27 views

Dynamically compute the union of polygons

Shorter version of my question: Is there any polygon union algorithm that allows me to change one of the polygons quickly? Longer version: Currently the major performance bottleneck I'm facing in one ...
3
votes
0answers
114 views

Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
1
vote
0answers
21 views

How to cover a surface with a predefined set of objects

I'm making a program that's supposed to be able to find pieces of wood in a dataset to cover a surface. For now I'm focusing on parallelepipedic shapes to simplify the problem (eventually I'd like it ...
2
votes
1answer
182 views

Merging all adjacent and overlapping rectangles in a grid to bigger rectangles

I have a 𝑛×𝑚 rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where ...
3
votes
0answers
35 views

How to get the minimal enclosed polyhedra in a Line framework (points connectivity lists)?

Greetings all and thank you. I'm a Ph.D. candidate working on a force structure's 3D tessellation project and get stuck. I've simplified the system into a set of lines linked together which formed a ...
4
votes
1answer
24 views

Binary Plane Partition: do we have to split a line segment?

I'm considering the planar BSP problem, where we are required to partition a set of disjoint line segments in the plane, such that every region in the partition contains at most one line segment or a ...
2
votes
1answer
27 views

Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
1
vote
1answer
26 views

Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...

1
2 3 4 5
16