clopen.solutions

Open problems

1108 registered problems.

OP-01068 Open
Voronoi diagram of lines in three dimensions
MG · lower envelopes · The Open Problems Project · Voronoi diagram of lines
OP-01069 Open
Union of fat objects in three dimensions
MG · fat objects · The Open Problems Project · union complexity
OP-01070 Open
Maximum number of k-sets
CO · halving lines · k-sets · The Open Problems Project
OP-01071 Open
Strongly polynomial linear programming
OC · linear programming · strongly polynomial algorithm · The Open Problems Project
OP-01072 Open
Point location in three-dimensional subdivisions
MG · point location · spatial subdivisions · The Open Problems Project
OP-01073 Open
Counting simple polygonalizations of a point set
CO · counting non-crossing Hamiltonian cycles · simple polygonalization · The Open Problems Project
OP-01074 Open
Recognizing visibility graphs of simple polygons
CO · simple polygon · The Open Problems Project · visibility graph recognition
OP-01075 Open
Complexity of vertical decompositions in five and more dimensions
MG · arrangements of surfaces · The Open Problems Project · vertical decomposition
OP-01076 Open
Subquadratic minimum-link paths among planar obstacles
MG · link distance · minimum-link path · The Open Problems Project
OP-01077 Open
Illuminating polygons with vertex π-floodlights
MG · art gallery problem · floodlight illumination · The Open Problems Project
OP-01078 Open
Hexahedral meshes compatible with a quadrilateral surface mesh
MG · hexahedral mesh · quadrilateral mesh · The Open Problems Project
OP-01079 Open
Flip-graph connectivity of tetrahedralizations in three dimensions
MG · flip graph · tetrahedralization · The Open Problems Project
OP-01080 Open
Hamiltonian tetrahedralizations of convex polytopes
MG · dual graph · Hamiltonian path · tetrahedralization · The Open Problems Project
OP-01081 Open
Maximum number of edges in a thrackle
CO · Conway's thrackle conjecture · graph drawing · The Open Problems Project · thrackle
OP-01082 Open
Trapping the light of a point source with segment mirrors
MG · light trapping · mirrors · polygonal billiards · The Open Problems Project
OP-01083 Open
Extending pseudosegment arrangements to pseudoline arrangements by subdivision
MG · pseudoline arrangements · pseudosegments · The Open Problems Project
OP-01084 Open
Complexity and approximation of the freeze-tag problem
OC · approximation algorithms · freeze-tag problem · NP-hardness · The Open Problems Project
OP-01085 Open
Compatible triangulations of point sets
MG · compatible triangulations · morphing · point sets · The Open Problems Project
OP-01086 Open
Pointed pseudotriangulations versus triangulations
CO · counting triangulations · pseudotriangulations · The Open Problems Project
OP-01087 Needs verification
Sorting X+Y
CO · pairwise sums · sorting X+Y · The Open Problems Project
OP-01088 Open
Vertex-unfolding polyhedra
MG · polyhedra · The Open Problems Project · vertex-unfolding
OP-01089 Open
General unfoldings of nonconvex polyhedra
MG · general unfolding · nonconvex polyhedra · The Open Problems Project
OP-01090 Needs verification
3-colorability of great-circle arrangements
CO · arrangements of great circles · graph coloring · The Open Problems Project · zonohedra
OP-01091 Open
Smallest universal point sets for planar graphs
CO · straight-line drawings of planar graphs · The Open Problems Project · universal point sets
OP-01092 Open
Two-bend 3D orthogonal point-drawings of graphs of maximum degree six
CO · 3D orthogonal graph drawing · bends · The Open Problems Project
OP-01093 Open
Planar Euclidean maximum traveling salesman problem
MG · Euclidean distances · maximum traveling salesman problem · The Open Problems Project
OP-01094 Open
Traveling salesman problem in solid grid graphs
CO · Hamiltonian cycle · solid grid graphs · The Open Problems Project · traveling salesman problem
OP-01095 Open
Complexity of the pallet loading problem
OC · computational complexity · pallet loading · rectangle packing · The Open Problems Project
OP-01096 Open
Chromatic number of the plane
CO · chromatic number of the plane · Hadwiger–Nelson problem · The Open Problems Project · unit-distance graph
OP-01097 Open
Three-colorings of the plane with no monochromatic congruent triangle
CO · Euclidean Ramsey theory · monochromatic triangle · plane coloring · The Open Problems Project
OP-01098 Needs verification
Transforming polygons into regular polygons by vertex-centroid moves
MG · polygon transformation · regular polygon · The Open Problems Project · vertex centroid
OP-01099 Open
Number of lines tangent to four unit balls
MG · combinatorial complexity · lines tangent to balls · line transversals · The Open Problems Project
OP-01100 Open
Volume-maximizing convex shape under perimeter-halving folding
MG · Alexandrov gluing · folding convex polygons · perimeter halving · The Open Problems Project
OP-01101 Open
Dynamic planar nearest neighbors in logarithmic time
MG · data structures · dynamic convex hull · dynamic nearest neighbor · The Open Problems Project
OP-01102 Open
Edge-unfolding polycubes
MG · edge unfolding · orthogonal polyhedra · polycubes · The Open Problems Project
OP-01103 Open
Reflexivity of planar point sets
MG · polygonization · reflexivity · reflex vertices · The Open Problems Project
OP-01104 Open
Rolling a die over a fully labelled board
CO · computational complexity · grid puzzle · rolling cube puzzle · The Open Problems Project
OP-01105 Open
Immersed spheres made of regular pentagons
MG · dodecahedra · polyhedral surface · regular pentagons · The Open Problems Project
OP-01106 Open
Slicing axis-parallel rectangles with few lines
CO · axis-parallel rectangles · independent set · piercing number · The Open Problems Project
OP-01107 Open
Edge-coloring complete geometric graphs without monochromatic crossings
CO · complete geometric graph · crossing edges · edge coloring · The Open Problems Project
OP-01108 Open
Zipper unfoldings of convex polyhedra
MG · convex polyhedra · Hamiltonian path · The Open Problems Project · zipper unfolding