Planar Convex Codes are Decidable

DOI10.1137/22M1511187arXiv2207.06290OpenAlexW4380485656MaRDI QIDQ6157969FDOQ6157969

Authors: Boris Bukh, R. Amzi Jeffs 

Publication date: 22 June 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2207.06290

Recommendations

• Complexity results for identifying codes in planar graphs
• Fast decoding of codes from algebraic plane curves
• scientific article
• 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 Keywords

decidabilityconvexrealizationsVenn diagramsconvex codesintersection patterns

Mathematics Subject Classification ID

Theory of error-correcting codes and error-detecting codes (94Bxx)

Cites Work

• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes
• d-collapsibility is NP-complete for d greater or equal to 4
• On open and closed convex codes
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
• Obstructions to convexity in neural codes
• What Makes a Neural Code Convex?
• Every binary code can be realized by convex sets
• Neural Codes, Decidability, and a New Local Obstruction to Convexity
• Embedding dimension phenomena in intersection complete codes
• Oriented matroids and combinatorial neural codes

Cited In (3)

• Every binary code can be realized by convex sets
• Title not available (Why is that?)
• Realizing convex codes with axis-parallel boxes

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)