The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves and surfaces.
Questions tagged [computational-geometry]
1221 questions
3
votes
1 answer
How to fit largest circle within Voronoi cells?
I have a list of Voronoi cells and would like to place the largest circle possible within each cell. What is the best way to do that?
Many thanks,
Arthur
3
votes
0 answers
How can I approximate a complicated polygon, such that the curvature never exceeds some set limit?
This question is inspired by CNC toolpath generation, although I've become interested in it from a more theoretical perspective as well; the practical answer may be to find a CAD software tool that does exactly what I'm asking, but I am more curious…
monguin
- 201
3
votes
3 answers
What is the best approach to find the nearest line segment (x1,y1), (x2,y2) from a point (x,y)?
Let's suppose the are three line segments in a plane, each line segment has coordinates (x1, y1) and (x2, y2). What is the best approach to find out the nearest line segment from a point (x, y)?
Hint: use vectors dot product.
Ahmad Shakir
3
votes
2 answers
Data structure to check if there are any points under query line segment
Let P be a set of points, where no three points are colinear and no two points have the same x- or y-coordinates. What is a good way of preprocessing P so that one can easily do queries in the below form:
Given a line segment q, are there any points…
Joe 2.0
- 31
- 2
3
votes
0 answers
Geometry: formula for 2D perspective transformation
Is there a way of describing an perspective transformation for one point in the 2dimenstion world?
I know you can write translation for one point for instance as: $(x*a,y*b) = (x',y')$ where $a$ describes the translation in the $X$ dimension and $b$…
flor1an
- 201
3
votes
5 answers
Precision in Programming Möbius transformations of the Riemann Sphere
Apologies if this is better asked on StackOverflow, but I thought the community here would be more likely to have an answer, even though it's related to coding.
I'm coding up a little library for experimenting with the inversive geometry of the…
John
- 180
3
votes
2 answers
What is a pseudodisk?
I'm reading a paper on computational geometry and the term pseudodisk popped up. A simple googling doesn't provide me with any mathematical definitions.
Could anyone please explain to me the definition of a pseudodisk?
Edit: For more context: "It…
Frederik Brinck Jensen
- 165
- 7
3
votes
2 answers
How to find the smallest enclosing quadrilateral for an irregular polygon
The context here is geo-location/geo-fencing. I need to compute the smallest enclosing quadrilaterals for a large sequence of irregular polygons (latitude/longitude value pairs) in order to approximately place a location in the right "polygon" with…
DroidOS
- 141
3
votes
3 answers
Shortest path in a maze
There is a maze, which is nothing but made of $2$ parallel polylines, which looks like a zig-zag road. We have to find the shortest path between the entrance and exit. Any ideas on how to proceed? Does it involve dynamic programming?
The maze can be…
V Shreyas
- 241
- 1
- 9
3
votes
1 answer
Maximum Side of a Square Dissected into Rectangles
Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set
$\{1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$.
Find the maximum value of $m$.
I…
Fawkes4494d3
- 2,984
3
votes
1 answer
Voronoi average number of vertices $< 6$
My text says "the average number of vertices of the Voronoi cells is less than six". Then it creates the vertex "at infinity", connects the half-infinite edges to this vertex and shows the equation: $$(v + 1) - e + n = 2$$ where v = number of…
PeteUK
- 1,570
2
votes
0 answers
Link and its Intersection
Let $K$ be a simplicial complex in $R^2$ such that $|K|$ is a simple polygon with inside.
An internal edge $ab \in K$ is an edge such that both of its two endpoints a and b are NOT on the boundary of $|K|$. Prove or disprove that:
link($ab$) =…
user2262504
- 954
2
votes
1 answer
Cover a polygon using a minimal set of rectangles
Given some polygon and rectangles all of a fixed height and width, how I can calculate the number and placement of the rectangles so that no point within or on the polygon is not contained within at least one rectangle. The rectangles are allowed to…
EvilAmarant7x
- 153
2
votes
0 answers
Length of the voronoi diagram
Does there exist an algorithm for computing the length of the voronoi diagram of a set of points or just gives the intersection points of the voronoi diagram?
mrk
- 3,075
2
votes
1 answer
Art Gallery Problem - is covering the edges enough?
The question is quite straight-forward but I can't seem to find the correct keywords to get my answer on the internet.
For those who are not familiar with the problem, given a polygon P we are asked to find the minimum number of guards which…
John Katsantas
- 820
- 5
- 15