11 papers
On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets
Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari +3
The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an ear…
Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers
Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6
Let be a set of points in , where is a constant, and let be a sequence of vertical hyperplanes that are sorted by their fi…
The Spanning Ratio of the Directed -Graph is 5
Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill +1
Given a finite set , the directed Theta-6 graph, denoted , is a well-studied geometric graph due to its close relationship with the Delaunay tria…
Noncrossing Longest Paths and Cycles
Greg Aloupis, Ahmad Biniaz, Prosenjit Bose +7
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short…
So Long Sucker: Endgame Analysis
Jean-Lou De Carufel, Marie Rose Jerade
So Long Sucker is a strategy board game that requires 4 players, each with chips of their designated color, and a board made of empty piles. With a clear set-up comes intri…
Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +1
Let be an edge-weighted graph, and let be a subgraph of . We say that is an -fault-tolerant -spanner for , if the following is true for any subset of at…