Diameter partitioning

DOI10.1007/BF02187699MaRDI QIDQ1076974zbMATH OpenOpenAlexFDO

Authors David Avis

Publication date 1986

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

Full work available at URL https://eudml.org/doc/130994

zbMATH Keywords

algorithmdiameterpartition of point sets

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10)

Review text

Given a set P of points, the diameter of P is the maximum distance of two points from P. In the paper, point sets are partitioned into two subsets satisfying certain requirements on the diameters, and cardinalities or displacement. The problems investigated about such partitions have algorithmic character.

Recommendations

• Minimizing the sum of diameters efficiently
• Optimal separable partitioning in the plane
• scientific article; zbMATH DE number 867650
• On a partition into convex polygons
• A parallel algorithm for partitioning a point set to minimize the maximum of diameters

Cites work

• Algorithms for high dimensional stabbing problems
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (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?)
• Non-partitionable point sets
• On the number of line separations of a finite set in the plane
• Optimal packing and covering in the plane are NP-complete
• Polygon Retrieval
• Space searching for intersecting objects
• Stabbing line segments
• The NP-completeness column: An ongoing guide

Cited in

(17)

• Minimizing the sum of diameters efficiently
• Geometric clustering in normed planes
• Some clustering algorithms in normed planes
• Polyhedral line transversals in space
• Computing grasp functions
• EFFICIENT PARALLEL RANGE SEARCHING AND PARTITIONING ALGORITHMS*
• A novel dynamic minimum spanning tree based clustering method for image mining
• OPTIMAL LINE BIPARTITIONS OF POINT SETS
• Free-form surface partition in 3-d
• New Algorithms for k-Center and Extensions
• Duality Relationships for a Partitioning Problem
• A parallel algorithm for partitioning a point set to minimize the maximum of diameters
• On the partition of plane sets into 6 subsets of small diameter
• Optimal line bipartitions of point sets
• New algorithms for \(k\)-center and extensions
• Computing Euclidean maximum spanning trees
• Algorithms for high dimensional stabbing problems

This page was built for publication: Diameter partitioning

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