Exact and heuristic algorithms for dynamic tree simplification

Carlos Correa, Ivan Marsic, Xiaodong Sun

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The Tree Knapsack Problem (TKP) is a 0-1 integer programming problem where hierarchy constraints are enforced. If a node is selected for packing into the knapsack, all the ancestor nodes on the path from the root to the selected node are packed as well. One apparent application of this problem is the simplification of computer graphics models. Real applications also use alternative representations of the nodes or whole subtrees, called impostors, to provide simplified trees that are visually acceptable. To account for this simplification, we introduce a generalized TKP, called Exclusive Multiple Choice Tree Knapsack Problem (EMCTKP). We present a dynamic programming algorithm to solve EMCTKP and a heuristic, called Lazy Iterative Arrangement, which reuses previous EMCTKP solutions to solve new instances of the problem. We show that this algorithm and heuristic reduce significantly the computation time of EMCTKP problems when changes in their parameters have spatial and temporal coherence. We also compare our algorithm with commercial integer programming solvers, and show that in our case the computation time grows linearly with the size of the problem tree and the available resources, while for generic IP solvers it is unpredictable and varies over a wide range of values.

Original languageEnglish (US)
Pages (from-to)331-353
Number of pages23
JournalJournal of Mathematical Modelling and Algorithms
Volume4
Issue number4
DOIs
StatePublished - Dec 2005

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Applied Mathematics

Keywords

  • Dynamic programming
  • Structured data simplification
  • Virtual worlds

Fingerprint

Dive into the research topics of 'Exact and heuristic algorithms for dynamic tree simplification'. Together they form a unique fingerprint.

Cite this