Axioms and hulls

DOI10.1007/3-540-55611-7zbMATH Open0777.68012OpenAlexW4235282062WikidataQ55951484 ScholiaQ55951484MaRDI QIDQ1202183FDOQ1202183

Authors: Donald E. Knuth 

Publication date: 23 January 1993

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55611-7

Recommendations

• scientific article; zbMATH DE number 4032498
• scientific article; zbMATH DE number 3974322
• scientific article; zbMATH DE number 1003230
• Computational Geometry in C
• Primitives for the manipulation of general subdivisions and the computation of Voronoi

zbMATH Keywords

Delaunay triangulationsaxiomatic predicate systemdegeneracy removal techniquesparsimonious algorithmsuniform oriented matroidsvortex-free tournaments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (only showing first 100 items - show all)

• Computer solution to the 17-point Erdős-Szekeres problem
• Improved deterministic parallel integer sorting
• Formal specification and proofs for the topology and classification of combinatorial surfaces
• A SAT attack on the Erdős-Szekeres conjecture
• Designing and proving correct a convex hull algorithm with hypermaps in Coq
• Matroids from modules
• Towards optimal parallel bucket sorting
• Fast formal proof of the Erdős-Szekeres conjecture for convex polygons with at most 6 points
• Ramsey numbers and monotone colorings
• Polyhedra genus theorem and Euler formula: A hypermap-formalized intuitionistic proof
• A characterization of heaps and its applications
• On Delaunay oriented matroids for convex distance functions
• On the computation of units and class numbers by a generalization of Lagrange's algorithm
• Permutation statistics and \((k,\ell)\)-hook Schur functions
• Qualitative reasoning with directional relations
• Enumerating topological \((n_k)\)-configurations
• Condorcet domains of tiling type
• Multitriangulations, pseudotriangulations and primitive sorting networks
• The ring of \(k\)-regular sequences
• The use and usefulness of numeration systems
• A note on some tree similarity measures
• A combinatorial version of Sylvester's four-point problem
• Efficient enumeration of all ladder lotteries and its application
• XSAT and NAE-SAT of linear CNF classes
• Enumeration of simple complete topological graphs
• A note on some algorithms for matroids
• On maximal weakly separated set-systems
• Plücker environments, wiring and tiling diagrams, and weakly separated set-systems
• Static competitive facility location: an overview of optimisation approaches.
• Principal \(\Gamma\)-cone for a tree
• q-hook length formulas for forests
• On Some SAT-Variants over Linear Formulas
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• The expected linearity of a simple equivalence algorithm
• The sorting order on a Coxeter group.
• An adaptive subdivision method for root finding of univariate polynomials
• Resurrecting the asymptotics of linear recurrences
• Creating order in sequence spaces with simple machines
• Mahonian statistics on labeled forests
• A survey of techniques in applied computational complexity
• A new measure of presortedness
• Exploiting few inversions when sorting: Sequential and parallel algorithms
• Grassmannians and pseudosphere arrangements
• Geodesic order types
• Sweeps, arrangements and signotopes
• Swapping labeled tokens on graphs
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• The node visit cost of brother trees
• On the relationship between son-trees and symmetric binary B-trees
• The method of creative telescoping
• Multitriangulations as complexes of star polygons
• Split sequence hash search
• The properties of random trees
• LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies
• Formalizing generalized maps in Coq
• Design and formal proof of a new optimal image segmentation program with hypermaps
• Optimal heapsort algorithm
• A scheme for constructing ordered minimal perfect hashing functions
• On the number of simple arrangements of five double pseudolines
• Coding and counting arrangements of pseudolines
• Computing pseudotriangulations via branched coverings
• On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3
• Why is the 3D Delaunay triangulation difficult to construct?
• Reprint of: Extreme point and halving edge search in abstract order types
• Parallel hashing algorithms
• Enumeration of Gelfand-Cetlin type reduced words
• Extreme point and halving edge search in abstract order types
• Enumeration, Counting, and Random Generation of Ladder Lotteries
• Convex hulls of random order types
• Computational geometry and discrete computations
• New algorithms and bounds for halving pseudolines
• Bicolored order types
• Optimal reconfiguration of optimal ladder lotteries
• Arrangements of pseudocircles: on circularizability
• Cambrian acyclic domains: counting \(c\)-singletons
• Cell complexes, oriented matroids and digital geometry.
• Two extensions of the Erdős-Szekeres problem
• On unimodular tournaments
• Every bit counts: the binary representation of typed data and programs
• An optimal algorithm for reconstructing point set order types from radial orderings
• Parking functions, valet functions and priority queues
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Exact computation of the sign of a finite sum
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Reconstructing point set order types from radial orderings
• On some extremal results for order types
• The complexity of order type isomorphism
• The Dirac-Goodman-Pollack conjecture
• A verified ODE solver and the Lorenz attractor
• Induced Ramsey-type results and binary predicates for point sets
• Implementing Euclid's straightedge and compass constructions in type theory
• A SAT attack on Erdős-Szekeres numbers in \(\mathbb{R}^d\) and the empty hexagon theorem
• Braid graphs in simply-laced triangle-free Coxeter systems are partial cubes
• Realization spaces of arrangements of convex bodies
• Topological art in simple galleries
• Combining Isabelle and QEPCAD-B in the Prover’s Palette
• A search problem on graphs which generalizes some group testing problems with two defectives
• Cycle action on treelike structures.
• Initial hulls and zero dimensional objects

This page was built for publication: Axioms and hulls

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