A fixed parameter algorithm for optimal convex partitions

DOI10.1016/J.JDA.2008.07.002MaRDI QIDQ1002101zbMATH OpenOpenAlexFDO

Authors Andreas Spillner

Publication date 23 February 2009

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.07.002

zbMATH Keywords

fixed-parameter algorithmconvex partition

Mathematics Subject Classification ID

Convex programming (90C25) Interior-point methods (90C51)

Recommendations

• A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
• Approximation Algorithms for the Minimum Convex Partition Problem
• Publication:4393369
• Publication:4519302
• Optimal partitions having disjoint convex and conic hulls
• Publication:3724092
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• A Convex Approach to Minimal Partitions

Cites work

• scientific article; zbMATH DE number 3767037 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
• A heuristic triangulation algorithm
• Algorithms and Computation
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• Minimum convex partition of a constrained point set
• Minimum weight triangulation is NP-hard
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• Parameterized and Exact Computation
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• The minimum weight triangulation problem with few inner points
• The traveling salesman problem with few inner points

Cited in

(18)

• A simplified convergence proof for the cone partitioning algorithm
• Tight Time Bounds for the Minimum Local Convex Partition Problem
• A note on the value in the disjoint convex partition problem
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• Solving the minimum convex partition of point sets with integer programming
• Conical partition algorithm for maximizing the sum of dc ratios
• Partition-Optimization with Schur Convex Sum Objective Functions
• An algorithm to maximize the agreement between partitions
• A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Minimum convex partition of a constrained point set
• Hardness and approximation of minimum convex partition
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• Minimum convex partition of point sets
• Application of the \texttt{DIRECT} algorithm to searching for an optimal \(k\)-partition of the set \(\mathcal {A}\subset \mathbb {R}^n\) and its application to the multiple circle detection problem
• Approximation Algorithms for the Minimum Convex Partition Problem
• A decision procedure for optimal polyhedron partitioning
• An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem

This page was built for publication: A fixed parameter algorithm for optimal convex partitions

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