Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
3
votes
2answers
157 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
4
votes
1answer
117 views

Check if intersection of several 2D half-planes is empty

I have a large set of half-planes $a_ix+b_iy + c_i \geq 0$. What I need is is the fastest way to determine if they have at least one common point. Currently I build a convex polygon by adding half-...
1
vote
1answer
84 views

Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$?

In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ and if it's negative, then $p_1$ is counter-...
2
votes
2answers
103 views

3D intersection algorithm for cylinders

The problem The input is a list of $N$ cylinders in 3D space, and the output should be a list of $M \leq N(N-1)/2$ pairs of cylinders that intersect. ($M$ depends on the input data, obviously.) If ...
2
votes
1answer
65 views

Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to. In the 2-dimensional case it's fairly ...
4
votes
2answers
362 views

Dynamic length of union of segments (1d Klee's measure problem)

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of ...
2
votes
1answer
69 views

In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following ...
2
votes
1answer
579 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?
2
votes
2answers
78 views

Compare two atan2

I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple ...
1
vote
0answers
19 views

How are epipolar lines useful in computer vision?

Why do use epipolar lines and what are it's benefits in computer vision ?I am unable to find the uses of epiploar lines and how they are helpful although i am aware of epiploar geometry concepts. I ...
3
votes
1answer
1k views

What are the primal and dual planes in the context of the point-line duality?

In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact ...
2
votes
1answer
865 views

How do I visit all edges incident to a vertex in a DCEL data structure?

In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which ...
0
votes
0answers
49 views

How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points

I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how ...
0
votes
0answers
9 views

Finding the point with smallest x-ordinate between two given y-ordinates [duplicate]

Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the ...
2
votes
0answers
38 views

Is there an algorithm for getting the boundary of a non-planar graph?

This is my first question here! If I have a non-planar graph where every vertex connects to 3 other vertices, and where the edges are allowed to intersect, how do I find the boundary of the graph? For ...
2
votes
1answer
92 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 ...
7
votes
3answers
142 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 ...
2
votes
2answers
154 views

Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain. The algorithm specifies splitting the edges at their ...
1
vote
1answer
34 views

Whats an elegant way to tour a hypercube, in distance order:

Consider the unit hypercube in $\mathbb{R}^n$ with all non-negative coordinates, and one point anchored at $0^n$. I've been working on a problem where I want to generate the (exponentially many) ...
3
votes
1answer
379 views

Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon

Let's say I give you the following array of points: (1,1) (1,3), (2,2), (4,1), (4,3) My (terrible) mspaint drawing of the shape that would be created by these looks like this: How, given an ...
1
vote
1answer
35 views

Recognizing a trajectory from a set

Given a set of 2d trajectories/paths, where a trajectory is a list of [x,y,time] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be ...
1
vote
1answer
137 views

CLRS closest-pair $L_m$ distances

I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following: We can define the distance between two points in ways other than euclidean. In the ...
3
votes
0answers
63 views

Calculating number of intersections of a horizontal line with line segments efficiently

I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $...
1
vote
2answers
61 views

Efficient rasterisation of vector image with polygons

Imagine I have a 2D area where I have many simple polygons ("simple" meaning not self-intersecting, they are not necessarily concave). A polygon is given to me as a series of points. I have ...
11
votes
3answers
402 views

Minimum circles to cover a set of points and avoid another set of points

Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in ...
5
votes
0answers
142 views

Is Geometric Disjoint Set Cover in P?

I have come across the following optimisation subproblem: Geometric Disjoint Set Cover. Consider a collection $C$ of (not necessarily distinct) ranges taken from a universe range $X \subset \mathbb{...
1
vote
1answer
28 views

3-Approximation for General position subset

I am currently studying for an exam and stumbled upon the following task: Given the following problem: Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$ Question Find the ...
2
votes
0answers
28 views

Efficient parameterization of low vertex count polygons

I'm trying to design a method to represent polygons as vectors. There are many ways to do this, but I have a few goals and I'm not sure what representation is best to fulfil these. The objectives are: ...
2
votes
1answer
54 views

Finding C-convex holes in a planar point set

I am looking for an efficient algorithm to find convex holes in a given point set. The problem is Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex ...
3
votes
1answer
558 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
683 views

Given a set of points in the plane all laying on the axis, find the number of right angled triangles

My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa)...
0
votes
1answer
1k views

Problem with storing an existing triangulation in a DCEL

I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure. Using the algorithm described in this answer, I was able to store a part ...
2
votes
2answers
2k views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
0
votes
1answer
45 views

Maximun distance that can be reached [duplicate]

A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, not necessarily unique, each described by a $vector$ of integer coordinates. The stone can make ...
4
votes
1answer
122 views

Evenly Spaced Points On Smooth Surface

I want to space points evenly (i.e. maximizing minimal distance between two points) on some smooth surface $S\subseteq\mathbf{R}^n$ (usually $n=3$), where I have a projection operator $p:\mathbf{R}^n\...
3
votes
1answer
376 views

Robust two lines/segments intersection point in 2D

Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide). There is a Wikipedia article which gives us exact ...
4
votes
1answer
90 views

Separating the snakes

In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal ...
7
votes
3answers
251 views

Find vertices of a convex polytope, defined by intersecting half-spaces

I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces that define it. In my special case the polytope is constructed by the ...
3
votes
0answers
71 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 ...
0
votes
2answers
266 views

Interpolation: How to generate 3D objects from 2D cross-sections?

Consider a sphere sitting on an $xy$-plane, and take 2D slices parallel to the $xy$-plane at various heights of z. Suppose we take 10 slices, evenly spaced along the $z$-axis, and now have 10 images ...
1
vote
1answer
158 views

Convert a polygon mesh into a b-spline surface

$\textbf{Problem:}$ Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly ...
9
votes
4answers
445 views

How to devise an algorithm to generate a random but valid train track layout?

I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those ...
3
votes
1answer
86 views

Triangulation of disjoint line segments

Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, ...
6
votes
0answers
113 views

Placing a tripod in a plane such that it partition a given set of points (with pic)

I would appreciate if anyone could help me with the following problem: Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
3
votes
2answers
91 views

Joining line segments to make tree

Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
3
votes
1answer
41 views

Prove vertices of polygon are endpoints of disjoint line segments

If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the ...
7
votes
2answers
152 views

Voronoi Diagram Drawing Variations and Charateristics

I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays. Similarly how can we draw the Voronoi diagram for the ...
5
votes
1answer
184 views

Near Triangulation Planar Graph

This is the problem I am dealing with: Given a set P of n points in general position, let a graph G be defined as follows: The vertex set is P. Two vertices, a and b, are joined by an edge provided ...
6
votes
1answer
121 views

Voronoi Cell and Voronoi Diagram

Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x ...
1
vote
1answer
275 views

Upper (or lower) envelope of some linear functions

Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function ...

1 2 3
4
5
15