The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
0answers
11 views

RGBD alignment without explicit transformation between RGB and depth

I have a set of RGB-D scans of the same scene, corresponding camera poses, intrinsics and extrinsics for both color and depth cameras. RGB's resolution is 1290x960, depth's is 640x480. Depth is ...
0
votes
0answers
24 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
2
votes
0answers
21 views

How to find a path in maze with navigator physical size constraints?

Assuming a 2D maze, how would one go about solving it for rigid 2D object moving through it? Additional specification: The object shape - it is a single entity, not a swarm/fleet. A shape of ...
2
votes
1answer
37 views

Efficient data structure for matching 3D lines

I'd like to Store a set of many infinite undirected 3D lines. Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?" The incidence-...
2
votes
0answers
42 views

Hexagon packing algorithm

I'm trying to pack hexagons, within bigger hexagons, as shown here: For this example, I have 5 "children" to put in my "father" hexagon. Each time I've got too many children, I would like to reduce ...
1
vote
2answers
111 views

Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the ...
0
votes
2answers
28 views

Efficient algorithm to filter off points from a point cloud

I have a master point cloud, which essentially just a list of points with {x,y} coordinates. The point cloud is HUGE ( like, it can contain more than 1 million ...
6
votes
1answer
50 views

Perpendicular vectors out of a set

I stumbled on this problem and I wanna know if there is a better solution. There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. ...
0
votes
0answers
10 views

Segment 3d mesh into multiple 3d meshes with equal size

Given a 3d mesh, for example the stanford bunny, how can I segment the mesh in a way that each segment has a roughly equal size between them? Assuming the target number of segments is given as an ...
3
votes
0answers
59 views

High-dimensional geometry and P vs. NP

Background: Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered ...
2
votes
0answers
55 views

Measuring the Union of Products of Intervals

Verbose Motivation for this Question Inspired by this paper about how the problem of counting unlabelled subtrees that are unique up to isomorphism is #P-complete, I was thinking about the problem ...
2
votes
0answers
29 views

Maximum and Minimum distance from query point within bounding box

I'm reading an article regarding approximating sums using KD-trees (similar to FMM). As part of the effort I'm trying to make sense of this article , which is cited. I'm having trouble understanding ...
2
votes
1answer
39 views

Finding the closest visible vertex among line segments

Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in ...
5
votes
1answer
84 views

Intersection of O(n) expanding circles with line from the origin

I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution. Consider yourself as a point located on the origin $(0,0)$ of an infinite two-...
0
votes
0answers
15 views

Configuration space for multi robot system

I have a problem that I think can be casted in the following way. Suppose I have a simple closed polygon $\mathcal{P}$ and $n$ squares (bounding boxes) $\mathcal{B}_1, \ldots, \mathcal{B}_n$, you can ...
0
votes
0answers
28 views

Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
0
votes
0answers
16 views

Review of fast 2D strip packing algorithms?

It seems to me that strip/bin packing algorithms must balance between two criterion: 1) how long it takes to perform the packing 2) how area-efficient the packing is (i.e. how minimal wasted area is)...
0
votes
1answer
49 views

Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$. For $n=1$ we ...
0
votes
0answers
17 views

How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...
1
vote
0answers
22 views

Circle fitting with fixed radius using algorithm by Chernov

I am doing a project where circle fitting is needed and I came across an algorithm and code found on the website (https://people.cas.uab.edu/~mosya/cl/CPPcircle.html) which works very well. My ...
3
votes
0answers
85 views

Help understanding how to make a simple 3D minimum bounding sphere?

I need to develop a minimum bounding sphere. It'll only ever be in 3 dimensions, and the numbers of points are relatively small (500-5000 total). Performance is important however. I was looking for ...
0
votes
0answers
29 views

What does W1 and W2-hardness imply?

Is there any simple definition to understand W1-hardness $\&$ W2- hardness in complexity theory? What I understood, that is the following: Let $\Pi$ be a decision problem with parameter $k$, then $...
3
votes
1answer
69 views

Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons

I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons. There are some instructions on this page (see the heading ...
0
votes
1answer
65 views

Minimum Bounding Quadrilateral

In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners ...
0
votes
0answers
9 views

maximize Steiner vertices in graphs of diameter 3

Let $G=(V, E)$ be a simple connected graph of diameter 3 and $T \subseteq V$ be a set of terminal vertices in $G$. For any $T' \subseteq T$, $(V', E')$ denotes a subgraph of $G$ containing $T',$ ...
2
votes
1answer
64 views

Steiner tree problem in graphs of diameter 3

I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing ...
1
vote
0answers
13 views

Where is the epipole if one camera center is not in view of the other?

In the book multiple view geometry, the epipole is defined as follows: The epipole is the point of intersection of the line joining the camera centres (the baseline) with the image plane. ...
1
vote
0answers
23 views

Can breakpoints of the beachline move up in Fortune's algorithm?

In these slides describing Fortune's algorithm for constructing a Voronoi diagram, it is noted on page 7 that break points of the beach line can move upward. How is this so? In most of the cases I ...
0
votes
0answers
34 views

Delaunay to Voronoi … and back?

Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points. How about the other way around? Given a ...
2
votes
2answers
49 views

Checking whether there is k circles with common area

I have N circles with different radius and position in the plane. The problem is finding k circles which have a common area.Obviously this can be solved using Brute-Force in $O(N^k)$. Is there a more ...
2
votes
0answers
26 views

Overlay two Voronoi Diagrams and calculate membership and areas of intersecting polygons

I would like to generate a composite diagram of two Voronoi diagrams. I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered. Basically, I have ...
1
vote
1answer
25 views

How to calculate point in 3D space from multiple perspective

I have multiple camera in different points. I have their position and rotation as $(x,y,z)$ , $(\alpha,\beta,\gamma)$ or $( roll, pitch, yaw)$ . And I have output like this : Feed from camera-1, I ...
2
votes
2answers
51 views

How to find the nearest point in the coordinate system

There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 ...
1
vote
0answers
21 views

Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$. What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\...
0
votes
0answers
21 views

How Voronoi Tessellations and Scutoids can help in computation?

Recently I came across a computerphile video https://www.youtube.com/watch?v=FGiBHsUkVzU about the use of Voronoi Tessellations and Scutoids in computation. But the video just explains what are ...
1
vote
0answers
11 views

Approximate Matching - two plane geometries with n points

I'm trying to do approximate matching of one plane geometry with n points to a big set of other plane geometries. The aim is to get the closest shape (rotation and scale agnostic) My idea would be to ...
2
votes
1answer
23 views

Parallelization of priority queue-based algorithms

There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-...
0
votes
1answer
26 views

Geometric median of two disjoint sets of points lies on line between their respective medians

I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets ...
2
votes
0answers
18 views

Nested dissection vs kd-tree

Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
4
votes
0answers
54 views

Randomized algorithm to compute cover radius?

I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it. Let $C$ and $P$ be two sets of point in the plane , such ...
3
votes
0answers
49 views

DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely? I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
1
vote
0answers
73 views

Convex hull partition of a set of points

Given a set $S$ of $n$ points in $\mathbb R^2$, denote by $\mathrm{convb}(S)$ the boundary of the convex hull of $S$. Let \begin{align*} S_1 &= \mathrm{convb}(S)\\ S_{i+1} &= \mathrm{convb}\...
0
votes
1answer
17 views

Orthogonal range reporting with fixed upper rectangular corner

Consider the following special case of orthogonal range searching: Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, ...
3
votes
1answer
35 views

Find plane within margin of error of >50% of points

There are $N < 3\times10^4$ 3D points. At least 50% of them lie approximately in the same plane, i.e. the distance between the plane and each point is at most $p$. Find such a plane. Attempt: ...
0
votes
0answers
47 views

Vertices/segments graph to polygons

On a 2D plane there is a set of vertices V and segments S. Each segment has 2 vertices, and each vertex knows segments that use it. That creates a kind of a graph. I would like to find all polygons ...
0
votes
0answers
26 views

Draw lines according to a specific condition

We have an infinitely planar cartesian coordinate system on which $N$ points are plotted. Cartesian coordinates of the point $i$ are represented by $(X_i,Y_i)$. Now we want to draw $(N−1)$ line ...
0
votes
0answers
16 views

Dividing Regular n-polygon into k Pieces

I just encountered the following problem: $L:$ Given positive integers $n\geq 3,k\geq1$, decide whether it is possible to divide an $n$-polygon into $k$ equally shaped and equally sized pieces ...
3
votes
0answers
84 views

How to cover holes with disks of a fixed radius? [closed]

So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These ...
3
votes
0answers
54 views

Self intersection in a simple polygon

Suppose I have a simple polygon whose vertices are $p_1,\ldots,p_n$ each $p_i \in \mathbb{R}^2$. Suppose now I pick two distincts vertices $p_i,p_j, i\neq j$ Is there some algorithm I can use to test ...
0
votes
0answers
13 views

find internal rhombi from a list of lines defined by point tuples [duplicate]

I have a image like this: I have code to extract the lines in the form [x1,x2,y1,y2] Now i need to extract the internal rhombi, one could bruteforce combinations and check for intersections easily, ...