Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computational-geometry]

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

3
votes
0answers
28 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
49 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
14 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
32 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
28 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
24 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
14 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
72 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
45 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
80 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
41 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 ...
3
votes
0answers
129 views

Count horizontal segments that intersect with a vertical segment

I have a set of $n$ horizontal line segments. I want to preprocess them and store them in a data structure, so that given a vertical segment $Q$ I can efficiently count the number of line segments ...
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
74 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
79 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
56 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
17 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
26 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
71 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
137 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
74 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 ...
5
votes
1answer
58 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 ...
4
votes
1answer
74 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 ...
6
votes
1answer
57 views

Can one count the number of n points in m triangles in less than O(nm)?

We have n points given as $(x,y)$ coordinates and m triangles given as triples of $(x,y)$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The ...
2
votes
1answer
33 views

DCEL operations on quad-edges, Twin, Next, and Prev

Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (twin, next, ...
2
votes
2answers
374 views

Minimizing the maximum Manhattan distance

Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself. ...
0
votes
0answers
31 views

Find the smallest width annulus in O(n)

Given set of points (in the plane), find in a linear time the smallest width annulus (annulus is the region between two concentric circles) that contains all the points. Because of the time ...
4
votes
2answers
83 views

Add lines to star with fixed coordinates maximizing smallest angle

I have the following problem: There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change....
1
vote
0answers
38 views

Algorithm to determine paths that define shape of connected rectangles

Say you have a bunch of rectangles like these: They get organized into 3 distinct final shapes like this: As you can see, there are a few "complete contours", as in here: The way you figure out the ...
2
votes
2answers
69 views

Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?

Suppose I have $n$ horizontal segments in the plane (i.e. their end points share the same $y$ value). I want to determine if there exists a line that intersects all such segments. I think I can ...
1
vote
1answer
54 views

Is there an algorithm to find the minimal number of dimensions, given the distances between points?

Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$ where $\Vert \cdot \Vert$ is the ...
2
votes
1answer
73 views

Longest-path in a graph, where the path should be 'straight'

Is there any existing work done on finding paths that are geometrically straight? I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of ...
4
votes
1answer
56 views

Algorithm to separate circles to reduce collision the maximum between them

I'll try to do my best to explain this. I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot ...
15
votes
2answers
2k views

What is this data structure/concept where a plot of points defines a partition to a space

I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem. Basically it's a plot of points, and the ...
2
votes
0answers
43 views

An efficient algorithm to find a linear transformation between two ternary quadratic forms

Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms $$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\ Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$ over the field $\mathbb{F}...
2
votes
0answers
47 views

Find points that lie outside of a series of triangles

Suppose there are $n$ triangles on a 2D plane, which don't cross each other and have no common vertex. Suggest an algorithm that gets $n$ points and in $O(n \log n)$ determines the points that don't ...
3
votes
1answer
57 views

Prove that there always exists a line bisecting each of two point sets

A line $\ell$ for a set $S$ of points is bisecting if the open halfspaces on either side of $\ell$ contain at most $\frac{|S|}{2}$ points. Now given point sets $A$ and $B$ in the plane, prove that we ...
2
votes
1answer
24 views

Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate

Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape, is it ...
3
votes
2answers
244 views

Bucket computation, cutting array with lines

Given an NxN array, drawing a line from the edge's midpoint to the opposite field how can the N buckets be found covering the majority of the line's path? A visual aid: Is there a better way to ...
0
votes
1answer
29 views

How to find the angle of an arc to draw graphic

I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular ...
2
votes
1answer
73 views

Convert NURBS curve into Cubic Bezier Curve

From this: Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials. I don't understand ...
2
votes
1answer
100 views

Can I compute closest split pair of points where distance is strictly less than delta

I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "...
1
vote
1answer
37 views

Real RAM computational mode

Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
0
votes
0answers
12 views

Lower envelope surface for 3d surfaces

Are there any fast algorithms for computing the lower envelope surface for a parametric family of surfaces $f_{a,b}(x,y) = \frac{a-x}{b-y} + c$, where (a,b,c) are parameters.
0
votes
1answer
27 views

Point rank in 2D plane time complexity?

I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps: Compute the median of x-coordinates of all ...
1
vote
0answers
33 views

Transform Image Point to Azimuth and Elevation

I'm working on an object tracker where I need to report the azimuth and elevation of targets. Both values should be scaled from degrees to unsigned 32-bit integers. For now I can ignore lens ...
0
votes
0answers
32 views

Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

Problem I have $J$ matrices $C_{j}$, which are $K \times M$. Elements of each matrix $C_{j}$ are between 0 and 1. I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that: ...
4
votes
0answers
71 views

How to maintain completely dynamic convex hull quickly?

If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points) ...
2
votes
2answers
79 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...