Planar Convex Codes are Decidable
From MaRDI portal
Publication:6157969
Abstract: We show that every convex code realizable by compact sets in the plane admits a realization consisting of polygons, and analogously every open convex code in the plane can be realized by interiors of polygons. We give factorial-type bounds on the number of vertices needed to form such realizations. Consequently we show that there is an algorithm to decide whether a convex code admits a closed or open realization in the plane.
Recommendations
- Complexity results for identifying codes in planar graphs
- Fast decoding of codes from algebraic plane curves
- scientific article; zbMATH DE number 5761821
- On a code problem concerning planar acyclic graphs
- Structure and measure of a decidable class of two-dimensional codes
- Codes on planar Tanner graphs
- Discriminating codes in (bipartite) planar graphs
- LDPC codes generated by conics in the classical projective plane
- Partial permutation decoding for codes from finite planes
- scientific article; zbMATH DE number 165467
Cites work
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- Algorithms in real algebraic geometry
- Embedding dimension phenomena in intersection complete codes
- Every binary code can be realized by convex sets
- Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
- Neural codes, decidability, and a new local obstruction to convexity
- Obstructions to convexity in neural codes
- On open and closed convex codes
- Oriented matroids and combinatorial neural codes
- The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes
- What makes a neural code convex?
- \(d\)-collapsibility is NP-complete for \(d \geq 4\)
Cited in
(3)
This page was built for publication: Planar Convex Codes are Decidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157969)
