Given a set of point P is an element of R-2, we consider the well-known maxima problem, consisting of reporting the maxima (not dominated) points of P, in the dynamic setting of boundary updates. In this setting we allow insertions and deletions of points at the extremities of P: this permits to move a resizable vertical window on the point set. We present a data structure capable of answering maxima queries in optimal O(k) worst case time, where k is the size of the answer. Moreover we show how to maintain the data structure under boundary updates operation in O(log n) time per update. This is the first technique in a dynamic setting capable of both performing update operations and answering maxima queries in optimal worst case time.

Maintaining maxima under boundary updates / D'Amore, Fabrizio; Franciosa, Paolo Giulio; R., Giaccio; M., Talamo. - STAMPA. - 1203:(1997), pp. 100-109. (Intervento presentato al convegno 3rd Italian Conference on Algorithms and Complexity (CIAC 97) tenutosi a ROME, ITALY nel MAR 12-14, 1997).

Maintaining maxima under boundary updates

D'AMORE, Fabrizio;FRANCIOSA, Paolo Giulio;
1997

Abstract

Given a set of point P is an element of R-2, we consider the well-known maxima problem, consisting of reporting the maxima (not dominated) points of P, in the dynamic setting of boundary updates. In this setting we allow insertions and deletions of points at the extremities of P: this permits to move a resizable vertical window on the point set. We present a data structure capable of answering maxima queries in optimal O(k) worst case time, where k is the size of the answer. Moreover we show how to maintain the data structure under boundary updates operation in O(log n) time per update. This is the first technique in a dynamic setting capable of both performing update operations and answering maxima queries in optimal worst case time.
1997
3rd Italian Conference on Algorithms and Complexity (CIAC 97)
04 Pubblicazione in atti di convegno::04c Atto di convegno in rivista
Maintaining maxima under boundary updates / D'Amore, Fabrizio; Franciosa, Paolo Giulio; R., Giaccio; M., Talamo. - STAMPA. - 1203:(1997), pp. 100-109. (Intervento presentato al convegno 3rd Italian Conference on Algorithms and Complexity (CIAC 97) tenutosi a ROME, ITALY nel MAR 12-14, 1997).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/243551
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact