Linear time algorithm for 1-center in R^d under convex polyhedral distance function

DOI10.1007/978-3-319-39817-4_5MaRDI QIDQ4632168zbMATH OpenOpenAlexFDO

Authors Sandip Das, Ayan Nandy, Swami Sarvottamananda

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-39817-4_5

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• On the 2-center problem under convex polyhedral distance function
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions
• A linear time algorithm for the computation of some distance functions between convex polygons
• Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions

Cites work

• A combinatorial bound for linear programming and related problems
• A subexponential bound for linear programming
• Linear Programming in Linear Time When the Dimension Is Fixed
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• Minimal enclosing discs, circumcircles, and circumcenters in normed planes. I.
• Minimal enclosing discs, circumcircles, and circumcenters in normed planes. II.
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• On bisectors for different distance functions
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

Cited in

(5)

• An improvement and an extension of the Elzinga \& Hearn's algorithm to the 1-center problem in \(\mathbb{R}^ n\) with \(l_{2b}\)-norms
• A linear time deterministic algorithm to find a small subset that approximates the centroid
• On the 2-center problem under convex polyhedral distance function
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions

This page was built for publication: Linear time algorithm for 1-center in \(\mathfrak {R}^d\) under convex polyhedral distance function

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