{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q790614","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q790614","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q790614","kernelVersion":"v1","immutable":true,"modified":"2026-01-05T15:01:00Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q790614","name":"Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles","headline":"Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles","description":"scientific article; zbMATH DE number 3848610","url":"https://portal.mardi4nfdi.de/entity/Q790614","datePublished":"1984-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1171388"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q161641"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1007/BF00264251","url":"https://doi.org/10.1007/BF00264251"},"sameAs":["https://doi.org/10.1007/BF00264251"],"comment":"We consider two geometrical problems that have been solved previously by linesweep algorithms: the measure problem and the contour problem. Both problems involve determining some property of the union of a set of rectangles, namely the size and the contour (boundary) of the union. We devise essentially a single time-optimal divide-and-conquer algorithm to solve both problems. This can be seen as a step towards comparing the power of the line-sweep and the divide-and-conquer paradigms. The suprisingly efficient divide-and-conquer algorithm is obtained by using a new technique called ''separational representation'', which extends the applicability of divide-and-conquer to orthogonal planer objects.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q4091421"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3049855"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3339305"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3323293"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5904922"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3336711"}]},"provenance":{"prov:generatedAtTime":"2026-01-05T15:01:00Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}