An in-place min-max priority search tree

被引:5
作者
De, Minati [1 ]
Maheshwari, Anil [2 ]
Nandy, Subhas C. [1 ]
Smid, Michiel [2 ]
机构
[1] Indian Stat Inst, Kolkata, India
[2] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada
来源
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2013年 / 46卷 / 03期
基金
加拿大自然科学与工程研究理事会;
关键词
Min-max priority search tree; In-place algorithm; Three-sided orthogonal range query; Maximum empty rectangle; LARGEST EMPTY RECTANGLE; SEGMENT INTERSECTION; ALGORITHM;
D O I
10.1016/j.comgeo.2012.09.007
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
One of the classic data structures for storing point sets in R-2 is the priority search tree, introduced by McCreight in 1985. We show that this data structure can be made in-place, i.e., it can be stored in an array such that each entry stores only one point of the point set and no entry is stored in more than one location of that array. It combines a binary search tree with a heap. We show that all the standard query operations can be performed within the same time bounds as for the original priority search tree, while using only O(1) extra space. We introduce the min-max priority search tree which is a combination of a binary search tree and a min-max heap. We show that all the standard queries which can be done in two separate versions of a priority search tree can be done with a single min-max priority search tree. As an application, we present an in-place algorithm to enumerate all maximal empty axis-parallel rectangles amongst points in a rectangular region R in R-2 in O(m log n) time with O(1) extra space, where m is the total number of maximal empty rectangles. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:310 / 327
页数:18
相关论文
共 50 条
  • [31] Generalized min-max programming problems subject to addition-min fuzzy relational inequalities
    Wu, Yan-Kuen
    Chiu, Ya-Ling
    Guu, Sy -Ming
    [J]. FUZZY SETS AND SYSTEMS, 2022, 447 : 22 - 38
  • [32] Min-max programming problem with constraints of addition-min-product fuzzy relation inequalities
    Qiu, Jianjun
    Yang, Xiaopeng
    [J]. FUZZY OPTIMIZATION AND DECISION MAKING, 2022, 21 (02) : 291 - 317
  • [33] Finding Minimal Solution to Generalized Min-Max Programming Problem With Addition-Min Composition
    Zhou, Xuegang
    Qin, Zejian
    [J]. IEEE ACCESS, 2024, 12 : 145174 - 145187
  • [34] Tri-composed fuzzy relation inequality with weighted-max-min composition and the relevant min-max optimization problem
    Wang, Zhining
    Zhu, Guocheng
    Yang, Xiaopeng
    [J]. FUZZY SETS AND SYSTEMS, 2024, 489
  • [35] Min-max consensus of multi-agent systems in random networks
    Li, Hailong
    Yang, Jianing
    Yin, Zhongjie
    Zhou, Liqi
    Xi, Jianxiang
    Zheng, Yuanshi
    [J]. NEUROCOMPUTING, 2024, 600
  • [36] A min-max vehicle routing problem with split delivery and heterogeneous demand
    Yakici, Ertan
    Karasakal, Orhan
    [J]. OPTIMIZATION LETTERS, 2013, 7 (07) : 1611 - 1625
  • [37] A differential evolution approach for solving constrained min-max optimization problems
    Segundo, Gilberto A. S.
    Krohling, Renato A.
    Cosme, Rodrigo C.
    [J]. EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (18) : 13440 - 13450
  • [38] Min-Max Optimal Control of Robot Manipulators Affected by Sensor Faults
    Milic, Vladimir
    Kasac, Josip
    Lukas, Marin
    [J]. SENSORS, 2023, 23 (04)
  • [39] Fixed Parameter Approximation Scheme for Min-Max k-Cut
    Chandrasekaran, Karthekeyan
    Wang, Weihang
    [J]. INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2021, 2021, 12707 : 354 - 367
  • [40] Min-Max and Two-Stage Possibilistic Combinatorial Optimization Problems
    Kasperski, Adam
    Zielinski, Pawel
    [J]. IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS (FUZZ 2011), 2011, : 2650 - 2655