Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
74 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
11 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
23 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
14 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
41 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
15 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
13 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
77 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
22 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
43 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
29 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
6 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
62 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
10 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
20 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
33 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
45 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
23 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
21 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
39 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
21 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
46 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
16 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
39 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
81 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
50 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, ...
3
votes
3answers
84 views

How to check if a list of XY coordinate meet the safety distance to each others?

My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I ...
3
votes
0answers
48 views

Calculating depth mask from different lighting

I have a object which is static, the camera is static and light source is moving. How can the depth mask be calculated ? Concept is to use - calculate height from shadow length Lets imagine a have ...
1
vote
0answers
32 views

Cover a polygon with least amount of parallelograms

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
1
vote
0answers
120 views

Inserting a new face in a Half Edge data structure (open-mesh and not)

I'm trying to figure how to implement face insertion in a halfedge data structure to represent 3D meshes, I think it's safe to assume I'll only deal with meshes that have disc topology. Although I've ...
2
votes
1answer
146 views

Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
0
votes
0answers
125 views

Area of Union Of Rectangles using Segment Trees

I'm trying to understand the algorithm that can be used to calculate the area of the union of a set of axis aligned rectangles. The solution that I'm following is here : http://tryalgo.org/en/...
3
votes
0answers
18 views

area of the projection of a mesh

Given: a quadrilateral mesh that forms the surface of a sphere a linear projection from 3D to 2D (a 2x3 matrix) The mesh is not convex in general, but it is regular enough that we know that the ...
1
vote
1answer
27 views

Closest k points - performance on large lists

Very similar to this Problem formulation: Given a list $L$ of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $...
1
vote
1answer
112 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
1
vote
1answer
156 views

An algorithm that find the max X/Y in a polygon in O(log n)

I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$. The polygon is represented by an array of its vertices where each vertex is represented by its ...
3
votes
1answer
75 views

Global indexing of shared nodes in parallel

Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of ...
6
votes
1answer
67 views

Partitioning connected graphs in the plane

This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes. How can we divide the plane using line segments in such a ...
5
votes
1answer
82 views

Smallest convex set containing given point

Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is ...