Algebraic k-sets and generally neighborly embeddings

DOI10.1007/S00454-021-00340-1MaRDI QIDQ2117359zbMATH OpenOpenAlexFDO

Authors Brett Leroux, Luis Rademacher

Publication date 21 March 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

convex bodies\(k\)-setreal algebraic varietiesVeronese embeddingneighborly polytopes\(k\)-facet

Mathematics Subject Classification ID

Real algebraic sets (14P05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Erd?s problems and related topics of discrete geometry (52C10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: Given a set $S$ of $n$ points in $mathbb{R}^d$, a $k$-set is a subset of $k$ points of $S$ that can be strictly separated by a hyperplane from the remaining $n-k$ points. Similarly, one may consider $k$-facets, which are hyperplanes that pass through $d$ points of $S$ and have $k$ points on one side. A notorious open problem is to determine the asymptotics of the maximum number of $k$-sets. In this paper we study a variation on the $k$-set/$k$-facet problem with hyperplanes replaced by algebraic surfaces. In stark contrast to the original $k$-set/$k$-facet problem, there are some natural families of algebraic curves for which the number of $k$-facets can be counted exactly. For example, we show that the number of halving conic sections for any set of $2n+5$ points in general position in the plane is $$. To understand the limits of our argument we study a class of maps we call emph{generally neighborly embeddings}, which map generic point sets into neighborly position. Additionally, we give a simple argument which improves the best known bound on the number of $k$-sets/$k$-facets for point sets in convex position.

Recommendations

• Point sets with many \(k\)-sets
• An upper bound on the number of planar K-sets
• \(k\)-sets and \(k\)-facets
• A class of point-sets with few \(k\)-sets
• \(k\)-sets and random hulls

Cites work

• scientific article; zbMATH DE number 5788282 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 3368644 (Why is no real title available?)
• scientific article; zbMATH DE number 3407703 (Why is no real title available?)
• An improved bound for k -sets in three dimensions
• An improved bound for \(k\)-sets in three dimensions
• An improved, simple construction of many halving edges
• Applications of random sampling in computational geometry. II
• Convex Bodies The Brunn-MinkowskiTheory
• Elementary structure of real algebraic varieties
• Improved bounds for planar \(k\)-sets and related problems
• Lectures on Polytopes
• Neighborly embedded manifolds
• New applications of random sampling in computational geometry
• On s -intersecting curves and related problems
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Point Selections and Weak ε-Nets for Convex Hulls
• Point sets with many k -sets
• Point sets with many \(k\)-sets
• Separation by convex pseudo-circles
• Separation by convex pseudo-circles (extended abstract)
• The Number of Halving Circles
• \(k\)-sets and \(k\)-facets
• \(k\)-sets in four dimensions

Cited in

(4)

• \(k\)-sets and \(k\)-facets
• In between \(k\)-sets, \(j\)-facets, and \(i\)-faces: \((i,j)\)-partitions
• -neighborhoods and comparison theorems
• The neat embedding problem for algebras other than cylindric algebras and for infinite dimensions

This page was built for publication: Algebraic \(k\)-sets and generally neighborly embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117359)