A Dynamic Algorithm for Placing Rectangles without Overlapping

スポンサーリンク

概要

• 論文の詳細を見る

• We consider the dynamic allocation problem of rectangles such that a mixed sequence of insertions and deletions of rectangles in a rectangular board is executed without any pair of rectangles overlapping each other. We present an O(n log log n) time algorithm for insertion of a rectangle if n rectangles have been already placed in the board. We solve the problem by reducing it to the contour construction problem on a special class of arrangements of rectangles.

• 一般社団法人情報処理学会の論文
• 1991-03-31

著者

• Asano T

  Chuo Univ. Tokyo Jpn

• Asano Takao

  Faculty Of Engineering Tohoku University

• Tsukiyama S

  Chuo Univ. Tokyo Jpn

• Tsukiyama Shuji

  Faculty Of Science And Engineering Chuo University

• TOKUYAMA TAKESHI

  IBM Research, Tokyo Research Laboratory

• Tokuyama Takeshi

  Ibm Research Ibm Tokyo Research Laboratory

• Tokuyama Takeshi

  Ibm Research Tokyo Research Laboratory

関連論文

• An Approximation Algorithm for the Hamiltonian Walk Problem on Maximal Planar Graphs (Graphs and Combinatorics III)
• A Hybrid Hierarchical Global Router for Multi-Layer VLSI's
• Parasitic Capacitance Modeling for Non-Planar Interconnects in Liquid Crystal Displays(Parasitics and Noise)(VLSI Design and CAD Algorithms)
• A Dynamic Algorithm for Placing Rectangles without Overlapping
• Practical Efficiencies of Planar Point Location Algorithms (Special Section on Discrete Mathematics and Its Applications)
• Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク