Skip to main content
Computer Science

Questions tagged [computational-geometry]

Ask Question

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

884 questions
Newest Active Bountied Unanswered
Filter by
Sorted by
Tagged with
1 vote
0 answers
18 views

I'm trying to process the protein data in the GNN, but had some questions about the data representation. The protein first is thought of as a graph. But there seemed to be different ways to encode ...
ShoutOutAndCalculate's user avatar
  • 165
4 votes
1 answer
138 views

I would like to find all the maximal rectangles contained in a rectilinear shape on a discrete grid. That is, every rectangle such that, if it were to grow by one cell in any direction, it would no ...
some guy's user avatar
  • 41
1 vote
0 answers
45 views

I recently learned about constructive solid geometry (CSG) which is concerned with defining geometrical shapes (let's assume them to be 3d) from constructors like cubes, spheres, ..., and operations ...
Turion's user avatar
  • 111
1 vote
0 answers
31 views

I have been trying to write a program to do the following: I have a function on a domain, D. The function is very complicated, but it is essentially zero in a significant part of the domain. Now, I ...
Physicist's user avatar
  • 11
3 votes
0 answers
90 views

As part of a larger project, I need to test if many points are contained within a zonohedron. As such I want a function that takes in a set of vectors, $v_1,\dots, v_n\in \mathbb{R}^3$, interpreted as ...
tox123's user avatar
  • 131
2 votes
1 answer
117 views

We have a dataset of 3d lines, each line is represented by a set of x,y,z coordinates. We wish to classify each of these 3d lines to one of 3 classes. In different words, we would like to know if a ...
AJ222's user avatar
  • 121
1 vote
1 answer
116 views

Given N segments that are parallel to either X or Y axis, count for each segment how many other segments it is intersecting with. Segments are considered intersecting if they share a common point. ...
Spirit's user avatar
  • 23
4 votes
2 answers
322 views

We are given a convex polygon $C = \{P_1, P_2, \dots, P_n\}$, where the points are ordered either clockwise or counter-clockwise. Additionally, we have a point $P_\text{new} = (x, y)$ that lies ...
amy's user avatar
  • 43
2 votes
1 answer
200 views

A grid is divided up into red cells (pixels), black cells, and white cells. We want to find the smallest boundary that: All red cells are within the boundary All cells of the boundary itself are ...
SRobertJames's user avatar
  • 83
1 vote
0 answers
74 views

I'm processing scans of printed pages. The books have drawings, photographs, print (which includes characters but also things like lines and boxes around them), and background (the white page). My ...
SRobertJames's user avatar
  • 83
1 vote
1 answer
73 views

Suppose you're given a population of $n$ points $(x_i, y_i)$ in the unit square $[0, 1]^2$. For a given new sample $(x, y)$, you must find the number of points in the original population satisfying $x\...
ego-thales's user avatar
  • 11
2 votes
0 answers
121 views

I have a problem where I need to cover marked cells in a 2D grid using rectangular boxes, with the goal of minimizing the total perimeter of the boxes. The rectangles can overlap, and they can also ...
Mahdi Khodabandeh's user avatar
  • 23
4 votes
0 answers
86 views

Given an arbitrary metric space $M=(X,d)$, is there a $(1+\epsilon)$-approximate algorithm (maybe probabilistic or randomized) that can estimate the diameter of $X$? This algorithm should be faster ...
user43464's user avatar
  • 141
1 vote
2 answers
603 views

Suppose we have $n$ lines in plane which is divided equally among the three sets(the lines in each set are equally spaced), each of contains $n/3$ lines. And they intersect each other and creates a ...
user avatar
4 votes
1 answer
289 views

Given a non-self-intersecting polygon made of straight segments how do you detect/trim sections of the polygon that are "thin"? If an algorithm exists for this, then great! If not, then... ...
Christopher Pratt's user avatar
  • 181

15 30 50 per page
1
2 3 4 5
…
59