Algebraic k-sets and generally neighborly embeddings

DOI10.1007/S00454-021-00340-1zbMATH Open1493.52016arXiv1912.03875OpenAlexW4205122189MaRDI QIDQ2117359FDOQ2117359

Authors: Brett Leroux, Luis Rademacher 

Publication date: 21 March 2022

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

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)